By Long Luo

15. 三數(shù)之和題目如下：

15. 三數(shù)之和

給你一個包含 n 個整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有和為 0 且不重復(fù)的三元組。

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

示例 1：
輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]

示例 2：
輸入：nums = []
輸出：[]

示例 3：
輸入：nums = [0]
輸出：[]

提示：
0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

方法一：暴力遍歷

思路與算法：

“不重復(fù)”的本質(zhì)是什么？

我們保持三重循環(huán)的大框架不變，只需要保證：

• 第二重循環(huán)枚舉到的元素不小于當(dāng)前第一重循環(huán)枚舉到的元素；
• 第三重循環(huán)枚舉到的元素不小于當(dāng)前第二重循環(huán)枚舉到的元素。

也就是說，我們枚舉的三元組滿足，保證了只有這個順序會被枚舉到，而、等等這些不會，這樣就減少了重復(fù)。要實(shí)現(xiàn)這一點(diǎn)，我們可以將數(shù)組中的元素從小到大進(jìn)行排序，隨后使用普通的三重循環(huán)就可以滿足上面的要求。

由于結(jié)果肯定會出現(xiàn)重復(fù)的數(shù)字，所以我們使用Set來去重，代碼如下所示：

public static List<List<Integer>> threeSum(int[] nums) {
    if (nums == null || nums.length < 3) {
        return new ArrayList<>();
    }

    Set<List<Integer>> res = new HashSet<>();
    int n = nums.length;
    // O(NLogN)
    Arrays.sort(nums);
    // O(N^3)
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    res.add(list);
                }
            }
        }
    }

    return new ArrayList<>(res);
}

復(fù)雜度分析：

• 時間復(fù)雜度：，其中N是數(shù)組的長度。
• 空間復(fù)雜度：。

方法二：排序 + 雙指針

思路與算法：

方法一肯定會超時，所以我們需要使用更好的方法。

使用雙指針的方法，將枚舉的時間復(fù)雜度從減少至。

為什么是呢？這是因?yàn)樵诿杜e的過程每一步中，左指針會向右移動一個位置，而右指針會向左移動若干個位置，這個與數(shù)組的元素有關(guān)，但我們知道它一共會移動的位置數(shù)為，均攤下來，每次也向左移動一個位置，因此時間復(fù)雜度為。

但考慮到問題的解決，代碼中需要注意一些去重技巧。

public static List<List<Integer>> threeSum(int[] nums) {
    if (nums == null || nums.length < 3) {
        return new ArrayList<>();
    }

    List<List<Integer>> ans = new ArrayList<>();
    int n = nums.length;
    Arrays.sort(nums);
    for (int i = 0; i < n - 2; i++) {
        if (nums[i] > 0) {
            break;
        }

        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        int left = i + 1;
        int right = n - 1;
        int target = -nums[i];
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum > target) {
                right--;
            } else if (sum < target) {
                left++;
            } else if (sum == target) {
                ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                //
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right + 1]) {
                    right--;
                }
            }
        }
    }

    return ans;
}

復(fù)雜度分析：

• 時間復(fù)雜度：，其中N是數(shù)組的長度。
• 空間復(fù)雜度：。

這道題我在做的時候，看了解題之后，對sum==target之后，一定要做left++; right--有點(diǎn)不解，不可以只left++或者right--嗎？

后來才想到，現(xiàn)在已經(jīng)sum==target，如果只處理一邊，那得到的不還是重復(fù)的數(shù)據(jù)嗎？所以需要兩邊操作，然后如果還是遇到重復(fù)的數(shù)字，那還需要繼續(xù)處理。

原文鏈接：15. 三數(shù)之和