LeetCode 16. 3Sum Closest [Medium] [C++] 解題筆記

這題給定一個 array 和一個 target value，要我們在 array 中找三個數其和最接近 target value。並且題目保證只有唯一一組解。

EX:

        nums = [-1,2,1,-4], target = 1

Ans: 2,  Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

想法:

        這題跟 15. 3Sum 很像，基本上都是同樣的作法，主要差別在於 15 必須要過濾掉相同的解，而這題基本上只會有一個解，因此只需要像 15 題一樣先固定一個數，然後在用 Two Pointer 找出剩下可能的組合並計算三數之和更新目前離 target 最近的值即可。

Complexity: O(nlogn + n^2) time.

完整程式碼:

class Solution {

public:

    int threeSumClosest(vector<int>& nums, int target) {

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

        int closest = 100000;

        for (int k = 0; k < nums.size() - 2; k++) {

            int complement = target - nums[k];

            int i = k + 1;

            int j = nums.size() - 1;

            while (i < j) {

                int sum = nums[i] + nums[j] + nums[k];

                int diff = target - sum;

                if (abs(target - closest) > abs(diff)) {

                    closest = sum;

                }

                if (closest == target) { return closest; }

                // if use this may omit the solution that i, j element have same value.

                // ex: [-1, 0, 1, 1, 55], target = 3, will omit solution 0, 1, 1

//while (i < j && nums[i] == nums[i + 1]) { i++; }

                //while (i < j && nums[j] == nums[j - 1]) { j--; }

                if (diff > 0) { i++; }

                else { j--; }

            }

        }

        

        return closest;        

    }

};