天天看點
傳回

一個函數秒殺 2Sum 3Sum 4Sum 問題

東哥帶你手把手撕力扣😏

點選下方卡片即可搜尋👇

經常刷 LeetCode 的讀者肯定知道鼎鼎有名的

twoSum

問題，我們的舊文 Two Sum 問題的核心思想 對

twoSum

的幾個變種做了解析。

但是除了

twoSum

問題，LeetCode 上面還有

3Sum

，

4Sum

問題，我估計以後出個

5Sum

，

6Sum

也不是不可能。

那麼，對于這種問題有沒有什麼好辦法用套路解決呢？本文就由淺入深，層層推進，用一個函數來解決所有

nSum

類型的問題。

一、twoSum 問題

力扣上的 twoSum 問題，題目要求傳回的是索引，這裡我來編一道 twoSum 題目，不要傳回索引，傳回元素的值：

如果假設輸入一個數組

nums

和一個目标和

target

，請你傳回

nums

中能夠湊出

target

的兩個元素的值，比如輸入

nums = [5,3,1,6], target = 9

，那麼算法傳回兩個元素

[3,6]

。可以假設隻有且僅有一對兒元素可以湊出

target

。

我們可以先對

nums

排序，然後利用前文「雙指針技巧彙總」寫過的左右雙指針技巧，從兩端相向而行就行了：

vector<int> twoSum(vector<int>& nums, int target) {
    // 先對數組排序
    sort(nums.begin(), nums.end());
    // 左右指針
    int lo = 0, hi = nums.size() - 1;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        // 根據 sum 和 target 的比較，移動左右指針
        if (sum < target) {
            lo++;
        } else if (sum > target) {
            hi--;
        } else if (sum == target) {
            return {nums[lo], nums[hi]};
        }
    }
    return {};
}

複制

這樣就可以解決這個問題，不過我們要繼續魔改題目，把這個題目變得更泛化，更困難一點：

nums

中可能有多對兒元素之和都等于

target

，請你的算法傳回所有和為

target

的元素對兒，其中不能出現重複。

函數簽名如下：

vector<vector<int>> twoSumTarget(vector<int>& nums, int target);

複制

比如說輸入為

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

，那麼算法傳回的結果就是：

[[1,3],[2,2]]

。

對于修改後的問題，關鍵難點是現在可能有多個和為

target

的數對兒，還不能重複，比如上述例子中

[1,3]

和

[3,1]

就算重複，隻能算一次。

首先，基本思路肯定還是排序加雙指針：

vector<vector<int>> twoSumTarget(vector<int>& nums, int target {
    // 先對數組排序
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int lo = 0, hi = nums.size() - 1;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        // 根據 sum 和 target 的比較，移動左右指針
        if      (sum < target) lo++;
        else if (sum > target) hi--;
        else {
            res.push_back({lo, hi});
            lo++; hi--;
        }
    }
    return res;
}

複制

但是，這樣實作會造成重複的結果，比如說

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

，得到的結果中

[1,3]

肯定會重複。

出問題的地方在于

sum == target

條件的 if 分支，當給

res

加入一次結果後，

lo

和

hi

不應該改變 1 的同時，還應該跳過所有重複的元素：

一個函數秒殺 2Sum 3Sum 4Sum 問題

是以，可以對雙指針的 while 循環做出如下修改：

while (lo < hi) {
    int sum = nums[lo] + nums[hi];
    // 記錄索引 lo 和 hi 最初對應的值
    int left = nums[lo], right = nums[hi];
    if (sum < target)      lo++;
    else if (sum > target) hi--;
    else {
        res.push_back({left, right});
        // 跳過所有重複的元素
        while (lo < hi && nums[lo] == left) lo++;
        while (lo < hi && nums[hi] == right) hi--;
    }
}

複制

這樣就可以保證一個答案隻被添加一次，重複的結果都會被跳過，可以得到正确的答案。不過，受這個思路的啟發，其實前兩個 if 分支也是可以做一點效率優化，跳過相同的元素：

vector<vector<int>> twoSumTarget(vector<int>& nums, int target) {
    // nums 數組必須有序
    sort(nums.begin(), nums.end());
    int lo = 0, hi = nums.size() - 1;
    vector<vector<int>> res;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        int left = nums[lo], right = nums[hi];
        if (sum < target) {
            while (lo < hi && nums[lo] == left) lo++;
        } else if (sum > target) {
            while (lo < hi && nums[hi] == right) hi--;
        } else {
            res.push_back({left, right});
            while (lo < hi && nums[lo] == left) lo++;
            while (lo < hi && nums[hi] == right) hi--;
        }
    }
    return res;
}

複制

這樣，一個通用化的

twoSum

函數就寫出來了，請確定你了解了該算法的邏輯，我們後面解決

3Sum

和

4Sum

的時候會複用這個函數。

這個函數的時間複雜度非常容易看出來，雙指針操作的部分雖然有那麼多 while 循環，但是時間複雜度還是

O(N)

，而排序的時間複雜度是

O(NlogN)

，是以這個函數的時間複雜度是

O(NlogN)

。

二、3Sum 問題

這是力扣第 15 題「三數之和」：

一個函數秒殺 2Sum 3Sum 4Sum 問題

題目就是讓我們找

nums

中和為 0 的三個元素，傳回所有可能的三元組（triple），函數簽名如下：

vector<vector<int>> threeSum(vector<int>& nums);

複制

這樣，我們再泛化一下題目，不要光和為 0 的三元組了，計算和為

target

的三元組吧，同上面的

twoSum

一樣，也不允許重複的結果：

vector<vector<int>> threeSum(vector<int>& nums) {
    // 求和為 0 的三元組
    return threeSumTarget(nums, 0);
}

vector<vector<int>> threeSumTarget(vector<int>& nums, int target) {
    // 輸入數組 nums，傳回所有和為 target 的三元組
}

複制

這個問題怎麼解決呢？很簡單，窮舉呗。現在我們想找和為

target

的三個數字，那麼對于第一個數字，可能是什麼？

nums

中的每一個元素

nums[i]

都有可能！

那麼，确定了第一個數字之後，剩下的兩個數字可以是什麼呢？其實就是和為

target - nums[i]

的兩個數字呗，那不就是

twoSum

函數解決的問題麼🤔

可以直接寫代碼了，需要把

twoSum

函數稍作修改即可複用：

/* 從 nums[start] 開始，計算有序數組
 * nums 中所有和為 target 的二進制組 */
vector<vector<int>> twoSumTarget(
    vector<int>& nums, int start, int target) {
    // 左指針改為從 start 開始，其他不變
    int lo = start, hi = nums.size() - 1;
    vector<vector<int>> res;
    while (lo < hi) {
        ...
    }
    return res;
}

/* 計算數組 nums 中所有和為 target 的三元組 */
vector<vector<int>> threeSumTarget(vector<int>& nums, int target) {
    // 數組得排個序
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<vector<int>> res;
    // 窮舉 threeSum 的第一個數
    for (int i = 0; i < n; i++) {
        // 對 target - nums[i] 計算 twoSum
        vector<vector<int>> 
            tuples = twoSumTarget(nums, i + 1, target - nums[i]);
        // 如果存在滿足條件的二進制組，再加上 nums[i] 就是結果三元組
        for (vector<int>& tuple : tuples) {
            tuple.push_back(nums[i]);
            res.push_back(tuple);
        }
        // 跳過第一個數字重複的情況，否則會出現重複結果
        while (i < n - 1 && nums[i] == nums[i + 1]) i++;
    }
    return res;
}

複制

需要注意的是，類似

twoSum

，

3Sum

的結果也可能重複，比如輸入是

nums = [1,1,1,2,3], target = 6

，結果就會重複。

關鍵點在于，不能讓第一個數重複，至于後面的兩個數，我們複用的

twoSum

函數會保證它們不重複。是以代碼中必須用一個 while 循環來保證

3Sum

中第一個元素不重複。

至此，

3Sum

問題就解決了，時間複雜度不難算，排序的複雜度為

O(NlogN)

，

twoSumTarget

函數中的雙指針操作為

O(N)

，

threeSumTarget

函數在 for 循環中調用

twoSumTarget

是以總的時間複雜度就是

O(NlogN + N^2) = O(N^2)

。

三、4Sum 問題

這是力扣第 18 題「四數之和」：

一個函數秒殺 2Sum 3Sum 4Sum 問題

函數簽名如下：

vector<vector<int>> fourSum(vector<int>& nums, int target);

複制

都到這份上了，

4Sum

完全就可以用相同的思路：窮舉第一個數字，然後調用

3Sum

函數計算剩下三個數，最後組合出和為

target

的四元組。

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    // 數組需要排序
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<vector<int>> res;
    // 窮舉 fourSum 的第一個數
    for (int i = 0; i < n; i++) {
        // 對 target - nums[i] 計算 threeSum
        vector<vector<int>> 
            triples = threeSumTarget(nums, i + 1, target - nums[i]);
        // 如果存在滿足條件的三元組，再加上 nums[i] 就是結果四元組
        for (vector<int>& triple : triples) {
            triple.push_back(nums[i]);
            res.push_back(triple);
        }
        // fourSum 的第一個數不能重複
        while (i < n - 1 && nums[i] == nums[i + 1]) i++;
    }
    return res;
}

/* 從 nums[start] 開始，計算有序數組
 * nums 中所有和為 target 的三元組 */
vector<vector<int>> 
    threeSumTarget(vector<int>& nums, int start, int target) {
        int n = nums.size();
        vector<vector<int>> res;
        // i 從 start 開始窮舉，其他都不變
        for (int i = start; i < n; i++) {
            ...
        }
        return res;

複制

這樣，按照相同的套路，

4Sum

問題就解決了，時間複雜度的分析和之前類似，for 循環中調用了

threeSumTarget

函數，是以總的時間複雜度就是

O(N^3)

。

四、100Sum 問題？

在 LeetCode 上，

4Sum

就到頭了，但是回想剛才寫

3Sum

和

4Sum

的過程，實際上是遵循相同的模式的。我相信你隻要稍微修改一下

4Sum

的函數就可以複用并解決

5Sum

問題，然後解決

6Sum

問題……

那麼，如果我讓你求

100Sum

問題，怎麼辦呢？其實我們可以觀察上面這些解法，統一出一個

nSum

函數：

/* 注意：調用這個函數之前一定要先給 nums 排序 */
vector<vector<int>> nSumTarget(
    vector<int>& nums, int n, int start, int target) {

    int sz = nums.size();
    vector<vector<int>> res;
    // 至少是 2Sum，且數組大小不應該小于 n
    if (n < 2 || sz < n) return res;
    // 2Sum 是 base case
    if (n == 2) {
        // 雙指針那一套操作
        int lo = start, hi = sz - 1;
        while (lo < hi) {
            int sum = nums[lo] + nums[hi];
            int left = nums[lo], right = nums[hi];
            if (sum < target) {
                while (lo < hi && nums[lo] == left) lo++;
            } else if (sum > target) {
                while (lo < hi && nums[hi] == right) hi--;
            } else {
                res.push_back({left, right});
                while (lo < hi && nums[lo] == left) lo++;
                while (lo < hi && nums[hi] == right) hi--;
            }
        }
    } else {
        // n > 2 時，遞歸計算 (n-1)Sum 的結果
        for (int i = start; i < sz; i++) {
            vector<vector<int>> 
                sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
            for (vector<int>& arr : sub) {
                // (n-1)Sum 加上 nums[i] 就是 nSum
                arr.push_back(nums[i]);
                res.push_back(arr);
            }
            while (i < sz - 1 && nums[i] == nums[i + 1]) i++;
        }
    }
    return res;
}

複制

嗯，看起來很長，實際上就是把之前的題目解法合并起來了，

n == 2

時是

twoSum

的雙指針解法，

n > 2

時就是窮舉第一個數字，然後遞歸調用計算

(n-1)Sum

，組裝答案。

需要注意的是，調用這個

nSum

函數之前一定要先給

nums

數組排序，因為

nSum

是一個遞歸函數，如果在

nSum

函數裡調用排序函數，那麼每次遞歸都會進行沒有必要的排序，效率會非常低。

比如說現在我們寫 LeetCode 上的

4Sum

問題：

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    // n 為 4，從 nums[0] 開始計算和為 target 的四元組
    return nSumTarget(nums, 4, 0, target);
}

複制

再比如 LeetCode 的

3Sum

問題，找

target == 0

的三元組：

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    // n 為 3，從 nums[0] 開始計算和為 0 的三元組
    return nSumTarget(nums, 3, 0, 0);        
}

複制

那麼，如果讓你計算

100Sum

問題，直接調用這個函數就完事兒了。

上一篇: tk.mybatis.mapper.MapperException: tk.mybatis.mapper.provider.EmptyProvider中缺少selectOne方法!
下一篇: Mybatis Plus --- 通用CRUDMybatis Plus — 通用CRUD