快捷導(dǎo)航

C++實(shí)現(xiàn)LeetCode(16.最近三數(shù)之和)

更新時(shí)間：2021年07月13日 09:23:40 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(16.最近三數(shù)之和),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 16. 3Sum Closest 最近三數(shù)之和

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).

這道題讓我們求最接近給定值的三數(shù)之和，是在之前那道 3Sum 的基礎(chǔ)上又增加了些許難度，那么這道題讓返回這個(gè)最接近于給定值的值，即要保證當(dāng)前三數(shù)和跟給定值之間的差的絕對(duì)值最小，所以需要定義一個(gè)變量 diff 用來(lái)記錄差的絕對(duì)值，然后還是要先將數(shù)組排個(gè)序，然后開(kāi)始遍歷數(shù)組，思路跟那道三數(shù)之和很相似，都是先確定一個(gè)數(shù)，然后用兩個(gè)指針 left 和 right 來(lái)滑動(dòng)尋找另外兩個(gè)數(shù)，每確定兩個(gè)數(shù)，求出此三數(shù)之和，然后算和給定值的差的絕對(duì)值存在 newDiff 中，然后和 diff 比較并更新 diff 和結(jié)果 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;
    }
};

我們還可以稍稍進(jìn)行一下優(yōu)化，每次判斷一下，當(dāng) nums[i]*3 > target 的時(shí)候，就可以直接比較 closest 和 nums[i] + nums[i+1] + nums[i+2] 的值，返回較小的那個(gè)，因?yàn)閿?shù)組已經(jīng)排過(guò)序了，后面的數(shù)字只會(huì)越來(lái)越大，就不必再往后比較了，參見(jiàn)代碼如下：

解法二：

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;
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(16.最近三數(shù)之和)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)最近三數(shù)之和內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: