[LeetCode] 15. 3Sum 三數(shù)之和

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
(-1, 0, 1)
(-1, -1, 2)

這道題讓我們求三數(shù)之和，比之前那道 Two Sum 要復(fù)雜一些，博主考慮過(guò)先 fix 一個(gè)數(shù)，然后另外兩個(gè)數(shù)使用 Two Sum 那種 HashMap 的解法，但是會(huì)有重復(fù)結(jié)果出現(xiàn)，就算使用 TreeSet 來(lái)去除重復(fù)也不行，會(huì) TLE，看來(lái)此題并不是考 Two Sum 的解法。來(lái)分析一下這道題的特點(diǎn)，要找出三個(gè)數(shù)且和為0，那么除了三個(gè)數(shù)全是0的情況之外，肯定會(huì)有負(fù)數(shù)和正數(shù)，還是要先 fix 一個(gè)數(shù)，然后去找另外兩個(gè)數(shù)，只要找到兩個(gè)數(shù)且和為第一個(gè) fix 數(shù)的相反數(shù)就行了，既然另外兩個(gè)數(shù)不能使用 Two Sum 的那種解法來(lái)找，如何能更有效的定位呢？我們肯定不希望遍歷所有兩個(gè)數(shù)的組合吧，所以如果數(shù)組是有序的，那么就可以用雙指針以線性時(shí)間復(fù)雜度來(lái)遍歷所有滿足題意的兩個(gè)數(shù)組合。

對(duì)原數(shù)組進(jìn)行排序，然后開(kāi)始遍歷排序后的數(shù)組，這里注意不是遍歷到最后一個(gè)停止，而是到倒數(shù)第三個(gè)就可以了。這里可以先做個(gè)剪枝優(yōu)化，就是當(dāng)遍歷到正數(shù)的時(shí)候就 break，為啥呢，因?yàn)閿?shù)組現(xiàn)在是有序的了，如果第一個(gè)要 fix 的數(shù)就是正數(shù)了，則后面的數(shù)字就都是正數(shù)，就永遠(yuǎn)不會(huì)出現(xiàn)和為0的情況了。然后還要加上重復(fù)就跳過(guò)的處理，處理方法是從第二個(gè)數(shù)開(kāi)始，如果和前面的數(shù)字相等，就跳過(guò)，因?yàn)椴幌氚严嗤臄?shù)字fix兩次。對(duì)于遍歷到的數(shù)，用0減去這個(gè) fix 的數(shù)得到一個(gè) target，然后只需要再之后找到兩個(gè)數(shù)之和等于 target 即可。用兩個(gè)指針?lè)謩e指向 fix 數(shù)字之后開(kāi)始的數(shù)組首尾兩個(gè)數(shù)，如果兩個(gè)數(shù)和正好為 target，則將這兩個(gè)數(shù)和 fix 的數(shù)一起存入結(jié)果中。然后就是跳過(guò)重復(fù)數(shù)字的步驟了，兩個(gè)指針都需要檢測(cè)重復(fù)數(shù)字。如果兩數(shù)之和小于 target，則將左邊那個(gè)指針i右移一位，使得指向的數(shù)字增大一些。同理，如果兩數(shù)之和大于 target，則將右邊那個(gè)指針j左移一位，使得指向的數(shù)字減小一些，代碼如下：

解法一：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        if (nums.empty() || nums.back() < 0 || nums.front() > 0) return {};
        for (int k = 0; k < (int)nums.size() - 2; ++k) {
            if (nums[k] > 0) break;
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            int target = 0 - nums[k], i = k + 1, j = (int)nums.size() - 1;
            while (i < j) {
                if (nums[i] + nums[j] == target) {
                    res.push_back({nums[k], nums[i], nums[j]});
                    while (i < j && nums[i] == nums[i + 1]) ++i;
                    while (i < j && nums[j] == nums[j - 1]) --j;
                    ++i; --j;
                } else if (nums[i] + nums[j] < target) ++i;
                else --j;
            }
        }
        return res;
    }
};

或者我們也可以利用 TreeSet 的不能包含重復(fù)項(xiàng)的特點(diǎn)來(lái)防止重復(fù)項(xiàng)的產(chǎn)生，那么就不需要檢測(cè)數(shù)字是否被 fix 過(guò)兩次，不過(guò)個(gè)人覺(jué)得還是前面那種解法更好一些，參見(jiàn)代碼如下：

解法二：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        set<vector<int>> res;
        sort(nums.begin(), nums.end());
        if (nums.empty() || nums.back() < 0 || nums.front() > 0) return {};
        for (int k = 0; k < (int)nums.size() - 2; ++k) {
            if (nums[k] > 0) break;
            int target = 0 - nums[k], i = k + 1, j = (int)nums.size() - 1;
            while (i < j) {
                if (nums[i] + nums[j] == target) {
                    res.insert({nums[k], nums[i], nums[j]});
                    while (i < j && nums[i] == nums[i + 1]) ++i;
                    while (i < j && nums[j] == nums[j - 1]) --j;
                    ++i; --j;
                } else if (nums[i] + nums[j] < target) ++i;
                else --j;
            }
        }
        return vector<vector<int>>(res.begin(), res.end());
    }
};

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

最新評(píng)論