016.3Sum Closest

Posted on | In

Solution 1: skipped

Brute force with 3 loops, time complexity O(n^3)

Solution 2: accepted 66%

Time:O(n^2), Space: O(1)
Two pointer solution, similar to Question 015, 3 Sum. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int len = nums.length;
        int gap = Integer.MAX_VALUE;
        int result = 0;
        if (len == 3)
          return nums[0] + nums[1] + nums[2];
        Arrays.sort(nums);
        for (int i = 0; i < len - 2; i++) {
            int j = i + 1;
            int k = len - 1;
            while (k > j) {
              int sum = nums[i] + nums[j] + nums[k];
              if (Math.abs(sum - target) < gap) {
                gap = Math.abs(sum - target);
                result = sum;
              }
              if (sum == target) {
                return sum;
              }
              else if (sum > target) {
                k--;
              }
              else {
                j++;
              }
            }
        }
        return result;
    }
}