Description

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.

Solution

Solve this problem by using three pointers.

Sort input nums.

Define res and initialize it's values to any 3 combination of nums. It'll hold our sought value.

Iterate the nums var. This loop's index, i, is the first pointer.

Within that loop, we initialize the next two pointers, left and right.

Loop while l is smaller than r.

Sum the values of nums[i] + nums[l] + nums[r] and compare it to target.

If the sum larger than target, decrement r. Otherwise increment l.

Check if the diff absolute value of cur minus target is less than diff of absolute value of res minus target.

If so, reassign res to cur.

Define response var, sort nums, iterate, return res

Initialize var which holds sought value, res, which we update while iterating through input nums.

Iterate the nums input. This loops incrementor i will be the first pointer.

Return res.

1// JS syntax is more flexible than statically typed languages
2// Input parameters don't require type annotation
3 
4var threeSumClosest = function(nums, target) {
5  var res = nums[0] + nums[1] + nums[2];
6  nums = nums.sort((a, b) => a - b);
7 
8  for (var i = 0; i < nums.length - 2; i ++) {
9  }
10  return res
11};

1// "nums: number[]" means input param is 'nums' is a list of numbers
2 
3function threeSumClosest(nums: number[], target: number): number {
4  var res = nums[0] + nums[1] + nums[2];
5  nums = nums.sort((a, b) => a - b);
6 
7  for (var i = 0; i < nums.length - 2; i ++) {
8  }
9  return res
10};

1// Dart requires typing return value, the 'int' before threeSumClosest.
2// It's parameters are also typed. The 'int' before target
3 
4class Solution {
5  int threeSumClosest(List<int> nums, int target) {
6    var res = nums[0] + nums[1] + nums[2];
7    nums.sort();
8 
9    for (var i = 0; i < nums.length - 2; i ++) {
10    }
11    return res;
12  }
13}

1// Java requires typing of input parameters and variables
2// Unlike TS the type comes before the param in function signature.
3 
4class Solution {
5    public int threeSumClosest(int[] nums, int target) {
6        int res = nums[0] + nums[1] + nums[2];
7        Arrays.sort(nums);
8 
9        for (int i = 0; i < nums.length - 2; i++) {
10        }
11 
12        return res;
13    }
14}

1# In Python3 typing for the function's signature and return value are optional
2 
3class Solution:
4  def threeSumClosest(self, nums: List[int], target: int) -> int:
5      nums.sort()
6      res = nums[0] + nums[len(nums) - 1] + nums[len(nums) - 2]
7 
8      for i, n in enumerate(nums):
9 
10      return res

1// := allows Go to infer type of 'res'
2// from the type of the expression on the right.
3 
4// Go also has type annotation on the right of the signature(like TS)
5 
6func threeSumClosest(nums []int, target int) int {
7  res := nums[0] + nums[1] + nums[2]
8  sort.Ints(nums[:])
9 
10  for i := 0; i < len(nums) - 2; i++ {
11  }
12 
13  return res
14}

Use i pointer to initialize next pointer and nest loop

Set l pointer to i + 1 and r to the length of nums - 1 In this way we can work our farthest left pointer from left to right and then have the next 2 pointers behave as a sliding window.

Loop while left is smaller than right.

In the loop, sum the values of nums[i] + nums[l] + nums[r].

Check this sum, if it matches target return cur as we can't get any closer to target.

Otherwise compare is it's greater than target of less and increment/decrement l and r as appropriate.

Remember, the idea here is we want the sum to be 0.

1var threeSumClosest = function(nums, target) {
2  var res = nums[0] + nums[1] + nums[2];
3  nums = nums.sort((a, b) => a - b);
4 
5  for (var i = 0; i < nums.length - 2; i ++) {
6    var l = i + 1
7    var r = nums.length - 1
8 
9    while (l < r) {
10      var cur = nums[i] + nums[l] + nums[r]
11      if (cur == target) return cur
12      if (cur > target) {
13        r -= 1
14      } else if (cur < target) {
15        l += 1
16      }
17    }
18  }
19  return res
20};

1function threeSumClosest(nums: number[], target: number): number {
2  var res = nums[0] + nums[1] + nums[2];
3  nums = nums.sort((a, b) => a - b);
4 
5  for (var i = 0; i < nums.length - 2; i ++) {
6    var l = i + 1
7    var r = nums.length - 1
8 
9    while (l < r) {
10      var cur = nums[i] + nums[l] + nums[r]
11      if (cur == target) return cur
12      if (cur > target) {
13        r -= 1
14      } else if (cur < target) {
15        l += 1
16      }
17    }
18  }
19  return res
20};

1class Solution {
2  int threeSumClosest(List<int> nums, int target) {
3    var res = nums[0] + nums[1] + nums[2];
4    nums.sort();
5 
6    for(var i = 0; i < nums.length - 2; i ++) {
7      var l = i + 1;
8      var r = nums.length - 1;
9 
10      while (l < r) {
11        var cur = nums[i] + nums[l] + nums[r];
12        if (cur == target) return cur;
13        if (cur > target) {
14          r -= 1;
15        } else if (cur < target) {
16          l += 1;
17        }
18      }
19    }
20    return res;
21  }
22}

1class Solution {
2    public int threeSumClosest(int[] nums, int target) {
3        int res = nums[0] + nums[1] + nums[2];
4        Arrays.sort(nums);
5 
6        for (int i = 0; i < nums.length - 2; i++) {
7            int l = i + 1;
8            int r = nums.length - 1;
9 
10            while (l < r) {
11                int cur = nums[i] + nums[l] + nums[r];
12 
13                if (cur > target) {
14                    r -= 1;
15                } else {
16                    l += 1;
17                }
18            }
19        }
20 
21        return res;
22    }
23}

1#
2 
3class Solution:
4  def threeSumClosest(self, nums: List[int], target: int) -> int:
5      nums.sort()
6      res = nums[0] + nums[len(nums) - 1] + nums[len(nums) - 2]
7 
8      for i, n in enumerate(nums):
9          l = i + 1
10          r = len(nums) - 1
11 
12          while l < r:
13              curSum = nums[i] + nums[l] + nums[r]
14 
15              if curSum == target:
16                  return curSum
17              if curSum > target:
18                  r -= 1
19              else:
20                  l += 1
21 
22      return res

1//
2 
3func threeSumClosest(nums []int, target int) int {
4  res := nums[0] + nums[1] + nums[2]
5  sort.Ints(nums[:])
6 
7  for i := 0; i < len(nums) - 2; i++ {
8    l := i + 1
9    r := len(nums) - 1
10 
11    for l < r {
12      cur := nums[i] + nums[l] + nums[r]
13      if cur > target {
14        r -= 1
15      } else {
16        l += 1
17      }
18    }
19  }
20 
21  return res
22}

Check the difference between cur and res

Compare the absolute different of cur - target and res - target to find which is closet to zero. If cur is smaller then reassign res to cur.

Use math's absolute in case the value becomes negative.

And finally optimize the outer loop comparing if the previous i is the same as this i. If so, continue to the next iteration.

1// Math.abs is helpful here.
2 
3var threeSumClosest = function(nums, target) {
4  var res = nums[0] + nums[1] + nums[2];
5  nums = nums.sort((a, b) => a - b);
6 
7  for (var i = 0; i < nums.length - 2; i ++) {
8    if (i > 0 && nums[i] == nums[i - 1]) {
9      continue
10    }
11    var l = i + 1
12    var r = nums.length - 1
13 
14    while (l < r) {
15      var cur = nums[i] + nums[l] + nums[r]
16      if (cur == target) return cur
17      if (cur > target) {
18        r -= 1
19      } else if (cur < target) {
20        l += 1
21      }
22 
23      if (Math.abs(cur - target) < Math.abs(res - target)) {
24        res = cur
25      }
26    }
27  }
28  return res
29};

1//
2 
3function threeSumClosest(nums: number[], target: number): number {
4  var res = nums[0] + nums[1] + nums[2];
5  nums = nums.sort((a, b) => a - b);
6 
7  for (var i = 0; i < nums.length - 2; i ++) {
8      if (i > 0 && nums[i] == nums[i - 1]) {
9          continue
10      }
11      var l = i + 1
12      var r = nums.length - 1
13 
14      while (l < r) {
15        var cur = nums[i] + nums[l] + nums[r]
16        if (cur == target) return cur
17        if (cur > target) {
18          r -= 1
19        } else if (cur < target) {
20          l += 1
21        }
22 
23        if (Math.abs(cur - target) < Math.abs(res - target)) {
24          res = cur
25        }
26      }
27  }
28  return res
29};

1//
2 
3class Solution {
4  int threeSumClosest(List<int> nums, int target) {
5    var res = nums[0] + nums[1] + nums[2];
6    nums.sort();
7 
8    for (var i = 0; i < nums.length - 2; i ++) {
9      if (i > 0 && nums[i] == nums[i - 1]) {
10          continue;
11      }
12      var l = i + 1;
13      var r = nums.length - 1;
14 
15      while (l < r) {
16        var cur = nums[i] + nums[l] + nums[r];
17        if (cur == target) return cur;
18        if (cur > target) {
19          r -= 1;
20        } else if (cur < target) {
21          l += 1;
22        }
23 
24        if ((cur - target).abs() < (res - target).abs()) {
25          res = cur;
26        }
27      }
28    }
29    return res;
30  }
31}

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

1# Python has abs as well.
2 
3class Solution:
4  def threeSumClosest(self, nums: List[int], target: int) -> int:
5      nums.sort()
6      res = nums[0] + nums[len(nums) - 1] + nums[len(nums) - 2]
7 
8      for i, n in enumerate(nums):
9          if (i > 0) and nums[i - 1] == nums[i]:
10              continue
11          l = i + 1
12          r = len(nums) - 1
13 
14          while l < r:
15              curSum = nums[i] + nums[l] + nums[r]
16 
17              if curSum == target:
18                  return curSum
19              if curSum > target:
20                  r -= 1
21              else:
22                  l += 1
23 
24              if abs(curSum - target) < abs(res - target):
25                  res = curSum
26 
27      return res

1// Go doesn't have built in support for mathematical abs
2// so we have to implement it ourselves.
3 
4func absInt(x int) int {
5  return absDiffInt(x, 0)
6}
7 
8func absDiffInt(x, y int) int {
9  if x < y {
10      return y - x
11  }
12  return x - y
13}
14 
15func threeSumClosest(nums []int, target int) int {
16    res := nums[0] + nums[1] + nums[2]
17    sort.Ints(nums[:])
18 
19    for i := 0; i < len(nums) - 2; i++ {
20      if i > 0 && nums[i] == nums[i - 1] {
21          continue
22      }
23 
24      l := i + 1
25      r := len(nums) - 1
26 
27      for l < r {
28        cur := nums[i] + nums[l] + nums[r]
29        if cur > target {
30          r -= 1
31        } else {
32          l += 1
33        }
34 
35        if absInt(cur - target) < absInt(res - target) {
36          res = cur
37        }
38      }
39    }
40 
41    return res
42}

Description

Solution

Define response var, sort nums, iterate, return res

Use i pointer to initialize next pointer and nest loop

Check the difference between cur and res

Conclusion