LeetCode 16. 3Sum Closest

LeetCode Problem No.16

No.15 is here

modalsoul.hatenablog.com

16. 3Sum Closest

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2

Input: nums = [0,0,0], target = 1
Output: 0

Code

object Solution {
  import scala.math.abs
  def threeSumClosest(nums: Array[Int], target: Int):Int = {
    val sorted = nums.sorted
    var result = Option.empty[Int]
    var i = 0
    while(i < nums.length-2) {
      val head = sorted(i)
      var left = i+1
      var right = nums.length-1
      while(left < right) {
        val sum = head+sorted(left)+sorted(right)
        if(sum == target) return target
        if(result.isEmpty || abs(target - sum) < abs(target - result.get)) result = Some(sum)
        if(sum < target) left = left+1
        else right = right-1
      }
      i = i+1
    }
    result.get
  }
}

Methods

This problem is similar to No. 15. modalsoul.hatenablog.com

• Sort given array.
• Take a variable(i) from array in order, and make sub-array(like tail)
  • Left starts with head of sub-array.
  • Right starts with last of sub-array.
  • If sum of triplets equals to target, fin.
  • If absolute value of sum of triplets is
    • under current result
      • Shift left
    • over current result
      • Shift right

Results

Runtime: 885 ms, faster than 70.83% of Scala online submissions for 3Sum Closest. Memory Usage: 68.7 MB, less than 62.50% of Scala online submissions for 3Sum Closest.