Algorithm Puzzles: 3Sum Closest

Posted on Edited on In Views: Word count in article: 267 Reading time ≈ 1 mins.

Algorithm Puzzles everyday every week sometimes: 3Sum Closest

Puzzle

Puzzle from leetcode:

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

Constraints:

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104

Solution

This puzzle is based on 3Sum, so I just made some slight changes base on 3Sum:

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
 public:
  int threeSumClosest(std::vector<int>& nums, const int target) {
    m_closetDiff = nums[0] + nums[1] + nums[2] - target;
    m_target = target;

    std::sort(nums.begin(), nums.end());

    for (int i = 0; i < nums.size() - 2; ++i) {
      if (m_closetDiff == 0) {
        break;
      }
      if (i >= 1 && nums[i] == nums[i - 1]) {
        continue;
      } else {
        twoPoint(nums, nums[i], i + 1, nums.size() - 1);
      }
    }

    return m_target + m_closetDiff;
  }

 private:
  int m_closetDiff;
  int m_target;

  void twoPoint(const std::vector<int>& nums, const int& stable,
                const int& left, const int& right) {
    if (left >= right) {
      return;
    }

    int diff = nums[left] + nums[right] + stable - m_target;

    if (std::abs(diff) < std::abs(m_closetDiff)) {
      m_closetDiff = diff;
    }

    int i = 0;
    if (diff < 0) {
      for (i = 1; i < right - left; ++i) {
        if (nums[left] != nums[left + i]) {
          break;
        }
      }
      twoPoint(nums, stable, left + i, right);
    } else {
      for (i = 1; i < right - left; ++i) {
        if (nums[right] != nums[left - i]) {
          break;
        }
      }
      twoPoint(nums, stable, left, right - i);
    }
  }
};