題目地址(3sum/">15. 三數之和)

https://leetcode.cn/problems/3sum/

題目描述

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

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

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

前置知識

• 雙指針法

公司

• 暫無

思路

• 雙指針法

關鍵點

• 1）去重，需要排序然后才方便判斷，第一個數和第二個數都需要判斷重復，我這里兩個去重方法都放在最后
• 2）最精妙之處，還是雙指針法，j = i + 1, k = n - 1（末尾）
  • 情況1.nums[j] + nums[k] < target，此時只需要j++即可
  • 情況2.nums[j] + nums[k] > target，此時k--即可
  • 關鍵問題，k--后，要不要還原k到n-1，答案是不用，因為數組已經排過序了，j++后，想要j,k位置兩數之和為target，k必然是一直--

代碼

• 語言支持：Java

Java Code:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        if (null == nums || n < 3) {
            return null;
        }
        // 依次將數組的第一個元素作為target，然后在剩下的數組尋找兩個之和為target的數
        List<List<Integer>> result = new ArrayList<>();
        // 排序是為了去重方便
        Arrays.sort(nums);
        for (int i = 0; i < n - 2;)  {
            // 雙指針法
            int j = i + 1;
            int k = n - 1;
            int target = - nums[i];
            while (j < k) {
                while (j < k && nums[j] + nums[k] > target) {
                    k--;
                }
                // 這里不能少了j < k，否則當j == k時，會一個位置取兩次
                if (j < k && nums[j] + nums[k] == target) {
                    result.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k])));  
                }
                j++;
                // 跳過重復的j
                while (j < k && nums[j] == nums[j - 1]) {
                    j++;
                }    
            }
            i++;
            while (i < n - 2 && nums[i] == nums[i - 1]) {
                i++;
            }
        }
        return result;
    }
}

Go code:

func threeSum(nums []int) [][]int {
    if (nums == nil || len(nums) < 3) {
        return nil
    }
    n := len(nums)
    // sort標準庫
    sort.Ints(nums)
    // 使用make，才能append
    result := make([][]int, 0)
    for i := 0; i < n - 2; {
        j, k, target := i + 1, n - 1, - nums[i]
        for j < k {
            for j < k && nums[j] + nums[k] > target {
                k--
            }

            if j < k && nums[j] + nums[k] == target {
                // append是builtin標準庫
                result = append(result, []int{nums[i], nums[j], nums[k]})
            }

            j++
            for j < k && nums[j] == nums[j - 1] {
                j++
            } 
        }
        i++
        for i < n - 2 && nums[i] == nums[i - 1] {
            i++
        }
    }
    return result
}

復雜度分析

令 n 為數組長度。

• 時間復雜度：
• 空間復雜度：就是排序的空間復雜度，如果需要復制，則是