?15. 三數(shù)之和

難度：中等

給你一個整數(shù)數(shù)組 nums ，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i != j、i != k 且 j != k ，同時還滿足 nums[i] + nums[j] + nums[k] == 0 。請

你返回所有和為 0 且不重復(fù)的三元組。

注意：答案中不可以包含重復(fù)的三元組。

示例 1：

輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
解釋：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元組是 [-1,0,1] 和 [-1,-1,2] 。
注意，輸出的順序和三元組的順序并不重要。

示例 2：

輸入：nums = [0,1,1]
輸出：[]
解釋：唯一可能的三元組和不為 0 。

示例 3：

輸入：nums = [0,0,0]
輸出：[[0,0,0]]
解釋：唯一可能的三元組和為 0 。

提示：

• $3<=nums.length<=3000$
• $?10^5<=nums[i]<=10^5$

??思路：雙指針

其實這道題目使用哈希法并不十分合適，因為在去重的操作中有很多細節(jié)需要注意，在面試中很難直接寫出沒有 bug 的代碼。
而且使用哈希法 在使用兩層 for 循環(huán)的時候，能做的剪枝操作很有限，雖然時間復(fù)雜度是$O(n^2)$，也是可以在leetcode上通過，但是程序的執(zhí)行時間依然比較長 。

這里使用雙指針法：

拿這個 nums 數(shù)組來舉例，首先將數(shù)組排序，然后有一層 for 循環(huán)，i 從下標(biāo) 0 的地方開始，同時定一個下標(biāo) left 定義在 i +1的位置上，定義下標(biāo) right 在數(shù)組結(jié)尾的位置上。
依然還是在數(shù)組中找到 a b c 使得 a + b +c = 0，我們這里相當(dāng)于 a = nums[i]，b = nums[left]，c = nums[right]:

• 如果 nums[i] + nums[left] + nums[right] > 0 就說明 此時三數(shù)之和大了，因為數(shù)組是排序后了，所以 right 下標(biāo)就應(yīng)該向左移動，這樣才能讓三數(shù)之和小一些
• 如果 nums[i] + nums[left] + nums[right] < 0 說明 此時 三數(shù)之和小了，left 就向右移動，才能讓三數(shù)之和大一些，直到 left 與 right 相遇為止。

答案中不可以包含重復(fù)的三元組，所以要考慮去重：

• 由于和為 0 ，所以只有三個數(shù)都為 0 時，才可能三個數(shù)同時相等，如果有這種情況，則加入結(jié)果，退出循環(huán)，因為后面的任意三個數(shù)都大于等于0；
• 每次循環(huán)三個數(shù)中的第一個數(shù) num[i] 都不同，避免重復(fù)。
• 如果后兩個相等，則只加這一種情況，退出循環(huán)；

??代碼：(Java、C++)

Java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length - 1;
        for(int i = 0; i < n - 1; i++){//遍歷到數(shù)組倒數(shù)第三個數(shù)即可
            if(nums[i] == 0){
                if(nums[i + 2] == 0){
                    ans.add(Arrays.asList(0, 0, 0));
                }
                break;
            }
            if(i > 0 && nums[i] == nums[i - 1]) continue; //去重，每次循環(huán)第一個數(shù)都不同

            int left = i + 1, right = n;
            
            while(left < right){
                if(nums[left] + nums[right] < -nums[i]) left++;
                else if(nums[left] + nums[right] > -nums[i]) right--;
                else{
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    if(nums[left] == nums[right]) break;//去重，后兩個相同則結(jié)束循環(huán)
                    while(left < right && nums[left + 1] == nums[left]) left++; //找到下一個比left大的數(shù)
                    left++;
                    while(left < right && nums[right - 1] == nums[right]) right--; //找到下一個比right小的數(shù)
                    right--;
                }
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int n = nums.size() - 1;
        for(int i = 0; i < n - 1; i++){
            if(nums[i] == 0) {
                if(nums[i + 2] == 0){
                    ans.push_back({0,0,0});
                }
                break;
            }
            if(i > 0 && nums[i] == nums[i - 1]) continue;//去重，每次循環(huán)第一個數(shù)都不同

            int left = i + 1, right = n;
            
            while(left < right){
                if(nums[left] + nums[right] < -nums[i]) left++;
                else if(nums[left] + nums[right] > -nums[i]) right--;
                else{
                    ans.push_back({nums[i], nums[left], nums[right]});
                    if(nums[left] == nums[right]) break;//去重，后兩個相同則結(jié)束循環(huán)
                    while(left < right && nums[left + 1] == nums[left]) left++;//找到下一個比left大的數(shù)
                    left++;
                    while(left < right && nums[right - 1] == nums[right]) right--;//找到下一個比right小的數(shù)
                    right--;
                }
            }
        }
        return ans;
    }
};

?? 運行結(jié)果：

?? 復(fù)雜度分析：

• 時間復(fù)雜度：$O(n^2)$，其中 n 為數(shù)組 nums 的長度。
• 空間復(fù)雜度：$O(1)$，忽略存儲答案的空間。

題目來源：力扣。

放棄一件事很容易，每天能堅持一件事一定很酷，一起每日一題吧！
關(guān)注我LeetCode主頁 / CSDN—力扣專欄，每日更新！文章來源地址http://www.zghlxwxcb.cn/news/detail-488795.html

注： 如有不足，歡迎指正！

到了這里，關(guān)于(雙指針 ) 15. 三數(shù)之和 ——【Leetcode每日一題】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！