2.15 3Sum Closest

Description

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Method

two pointers it is a 2sum closest fllow-up question we can for loop each elements from left to right, and do twosum closest to solve the problem.

Time and Space Complexity

o(n^2)

Code

public class Solution {

public int threeSumClosest(int[] nums, int target) {
       if (nums == null || nums.length == 0){
           return 0;
       }
       Arrays.sort(nums);
       int min = Integer.MAX_VALUE;
       int res = 0;
       for (int i = 0; i < nums.length - 2; i++){
            int sum = target - nums[i];
            int s = i + 1; 
            int e = nums.length - 1;
            while (s < e){
                  int tmp = nums[s] + nums[e];
                  if (tmp == sum){
                      return target;
                  } else if (tmp > sum){
                      if (tmp - sum < min){
                          min = tmp - sum;
                          res = tmp + nums[i];

                      }
                      e--;
                  } else {
                      if (sum - tmp < min){
                          min = sum - tmp;
                          res = tmp + nums[i];

                      }
                      s++;
                  }
            }
       }
       return res;
}

}