題目

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

1
2
3
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

1
2
3
Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

解釋題目

題目會給一個 integer array nums，和一個 integer targets。

在 nums 中找三個整數，這三個整數的總和，要最接近 target。

回傳三個整數的總和。

思路

  1. 先排序 nums，之後做雙指針比較好處理。
  2. 固定一項元素，再利用雙指針，找剩下的兩個元素，目標是三個元素的總和最接近 target。
  3. 如果 target 和 新計算的 sum 之間的距離有更小，則更新 result。
  4. 如果新計算的 sum ，比 target 小，則 left++ => 讓新計算的 sum 會更大，越接近 target
  5. 如果新計算的 sum ，比 target 大，則 right– => 讓新計算的 sum 會更小，越接近 target

這題跟 Leetcode-15 很像。

程式碼

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
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int result = 0;
        int distance = INT_MAX;

        for(int i = 0; i < nums.size(); i++){
            int fix = nums[i];
            int left = i + 1;
            int right = nums.size() - 1;
            while(left < right){
                int sum = fix + nums[left] + nums[right];
                if(distance > abs(target-sum)){
                    distance = abs(target-sum);
                    result = sum;
                }

                if(sum <= target)
                    left++;
                else
                    right--;
            }
        }

        return result;
    }
};

// target: 1
// -4, -1, 1, 2