/ Data Structure and Algorithms  

Leetcode 16: 3Sum Closest

Question



Similar to Question 15: 3Sum. This time we want to find the 3 sum that is closest to the target value.

Similar Questions

Solution 1

Brute force. We need 3 nested loop to get all possible sums, and then get the sum that is closest to the target. Time complexity is O(n3). Space complexity O(1).

Solution 2

We can make use of the similar idea of Question 15: 3Sum.

  1. Sort the array
  2. Loop the array to get the first number nums[i]
  3. Use 2 pointers head and tail to loop the remaining array (head = i + 1)
  4. sum = nums[i] + nums[head] + nums[tail]
  5. Depending on the comparison of sum and target:
    5.1 sum = target: then we can return the value as it as closest to the target
    5.2 sum < target: head++
    5.3 sum > target: tail--
  6. Use a variable to keep track of the smallest distance

Code:

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
// keep trakc of minimun distance
int distance = Integer.MAX_VALUE;
int result = 0;

// sort the array
Arrays.sort(nums);

for (int i = 0; i < nums.length; i++) {
    int low = i + 1;
    int high = nums.length - 1;

    // another loop with 2 pointers
    while (low < high) {
        int tempSum = nums[i] + nums[low] + nums[high];
        if (tempSum == target) {
            return tempSum;
        } else if (tempSum > target) {
            high--;
        } else {
            low++;
        }

        if (Math.abs(tempSum - target) < distance) {
            distance = Math.abs(tempSum - target);
            result = tempSum;
        }
    }
}

return result;

We are running 2 loops (O(n2)), and space complexity O(1).