默認(rèn)你已經(jīng)理解題意了哈

雙指針來解

雙指針法使用之前： 先把給定 nums 進(jìn)行排序，復(fù)雜度是 O(NlogN)

然后固定 3 個指針中最左（也就是最小數(shù)字）的指針 k，雙指針 i，j 分指向數(shù)組索引 (k,len(nums)) 兩端，然后用雙指針交替向中間移動，記錄每個固定指針 k 的所有滿足 nums[k] + nums[i] + nums[j] == 0 的 i,j 組合

如果是暴力法搜索為 O(N^3) 的時間復(fù)雜度，這種就很垮

1. 當(dāng) nums[k] > 0 時直接 break 跳出來：因為 nums[j] >= nums[i] >= nums[k] > 0，即 3 個數(shù)字都大于 0，在此固定指針 k 之后就不可能再找到結(jié)果了。
2. 當(dāng) k > 0且nums[k] == nums[k - 1]時就跳過這個元素nums[k]：因為已經(jīng)把 nums[k - 1] 的所有組合已經(jīng)加入到結(jié)果里面去了，所以本次雙指針只能搜索到重復(fù)組合。
3. i，j 分設(shè)在數(shù)組索引 (k, len(nums)) 兩端，當(dāng)i < j時循環(huán)計算s = nums[k] + nums[i] + nums[j]，并按照以下規(guī)則執(zhí)行雙指針移動：

• 當(dāng)s < 0時，i += 1并跳過所有重復(fù)的nums[i]；
• 當(dāng)s > 0時，j -= 1并跳過所有重復(fù)的nums[j]；
• 當(dāng)s == 0時，記錄組合[k, i, j]到res，并執(zhí)行i += 1和j -= 1，跳過所有重復(fù)的nums[i]和nums[j]，防止記錄到重復(fù)組合。

清晰圖解

復(fù)雜度分析下

• 時間復(fù)雜度是O(N^2)：其中固定指針k循環(huán)復(fù)雜度 O(N)O(N)，雙指針 i，j 復(fù)雜度 O(N)
• 空間復(fù)雜度是O(1)：指針只使用了常數(shù)大小的額外空間

//Javaz這樣來寫
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);//排序，nums變成遞增數(shù)組
        List<List<Integer>> res = new ArrayList<>();
      	//k < nums.length-2 是為了保證后面還能存在兩個數(shù)字
        for(int k = 0; k < nums.length - 2; k++){
            if(nums[k] > 0) break;//若nums[k]大于0,則后面的數(shù)字也是大于零（排序后是遞增的哦）
            if(k > 0 && nums[k] == nums[k - 1]) continue;//nums[k]值重復(fù)了，去重
            int i = k + 1, j = nums.length - 1;//定義左右指針
            while(i < j){
                int sum = nums[k] + nums[i] + nums[j];
                if(sum < 0){
                    while(i < j && nums[i] == nums[++i]);//左指針前進(jìn)并去重
                } else if (sum > 0) {
                    while(i < j && nums[j] == nums[--j]);//右指針后退并去重
                } else {
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
                    while(i < j && nums[i] == nums[++i]);//左指針前進(jìn)并去重
                    while(i < j && nums[j] == nums[--j]);//右指針后退并去重
                }
            }
        }
        return res;
    }
}

python代碼

//python這樣來寫
class Solution:
    def threeSum(self, nums: [int]) -> [[int]]:
        nums.sort()
        res, k = [], 0
        for k in range(len(nums) - 2):
            if nums[k] > 0: break # 1. because of j > i > k.
            if k > 0 and nums[k] == nums[k - 1]: continue # 2. skip the same `nums[k]`.
            i, j = k + 1, len(nums) - 1
            while i < j: # 3. double pointer
                s = nums[k] + nums[i] + nums[j]
                if s < 0:
                    i += 1
                    while i < j and nums[i] == nums[i - 1]: i += 1
                elif s > 0:
                    j -= 1
                    while i < j and nums[j] == nums[j + 1]: j -= 1
                else:
                    res.append([nums[k], nums[i], nums[j]])
                    i += 1
                    j -= 1
                    while i < j and nums[i] == nums[i - 1]: i += 1
                    while i < j and nums[j] == nums[j + 1]: j -= 1
        return res