C++實現LeetCode(16.最近三數之和)

Posted on by

[LeetCode] 16. 3Sum Closest 最近三數之和

Given an array nums of n integers 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:

Given array nums = [-1, 2, 1, -4], and target = 1.

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

這道題讓我們求最接近給定值的三數之和，是在之前那道 3Sum 的基礎上又增加瞭些許難度，那麼這道題讓返回這個最接近於給定值的值，即要保證當前三數和跟給定值之間的差的絕對值最小，所以需要定義一個變量 diff 用來記錄差的絕對值，然後還是要先將數組排個序，然後開始遍歷數組，思路跟那道三數之和很相似，都是先確定一個數，然後用兩個指針 left 和 right 來滑動尋找另外兩個數，每確定兩個數，求出此三數之和，然後算和給定值的差的絕對值存在 newDiff 中，然後和 diff 比較並更新 diff 和結果 closest 即可，代碼如下：

解法一：

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int closest = nums[0] + nums[1] + nums[2];
        int diff = abs(closest - target);
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 2; ++i) {
            int left = i + 1, right = nums.size() - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                int newDiff = abs(sum - target);
                if (diff > newDiff) {
                    diff = newDiff;
                    closest = sum;
                }
                if (sum < target) ++left;
                else --right;
            }
        }
        return closest;
    }
};

我們還可以稍稍進行一下優化，每次判斷一下，當 nums[i]*3 > target 的時候，就可以直接比較 closest 和 nums[i] + nums[i+1] + nums[i+2] 的值，返回較小的那個，因為數組已經排過序瞭，後面的數字隻會越來越大，就不必再往後比較瞭，參見代碼如下：

解法二：

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int closest = nums[0] + nums[1] + nums[2];
        int diff = abs(closest - target);
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 2; ++i) {
            if (nums[i] * 3 > target) return min(closest, nums[i] + nums[i + 1] + nums[i + 2]);
            int left = i + 1, right = nums.size() - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                int newDiff = abs(sum - target);
                if (diff > newDiff) {
                    diff = newDiff;
                    closest = sum;
                }
                if (sum < target) ++left;
                else --right;
            }
        }
        return closest;
    }
};

到此這篇關於C++實現LeetCode(16.最近三數之和)的文章就介紹到這瞭,更多相關C++實現最近三數之和內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：