題目
#

leetcode 15 - 3Sum (題目說明請點連結)

題目簡述
#

給定一個整數陣列，找出所有不重複的三數組，使得三個數字的和為零。

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 和為零的三數組是 [-1,-1,2] 和 [-1,0,1]。

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: 唯一可能的三數組不等於零。

解題思路
#

給定一個整數陣列，找出所有不重複的三數組，使得三個數字的和為零。
關鍵要求：

三數組中的三個數字和為 0
不能有重複的三數組
每個三數組中的數字可以重複使用（但三數組本身不能重複）

使用 Two Pointers 配合排序：

首先對陣列進行排序，方便去除重複的組合來搜尋
固定第一個數字 nums[i]，然後使用雙指針尋找剩下的兩個數字
左指針 j 從 i+1 開始，右指針 k 從陣列結尾開始
根據三數之和與 0 的比較來移動指針

對陣列進行排序
遍歷陣列，固定第一個數字 nums[i]
跳過重複的第一個數字（去重）
使用雙指針 j 和 k 尋找剩下的兩個數字：
- 如果 nums[i] + nums[j] + nums[k] == 0：加入結果並跳過重複元素
- 如果 nums[i] + nums[j] + nums[k] > 0：移動右指針 k--
- 如果 nums[i] + nums[j] + nums[k] < 0：移動左指針 j++
重複步驟2-4直到遍歷完所有數字

例子說明
#

以 nums = [-1,0,1,2,-1,-4] 為例，排序後為 [-4,-1,-1,0,1,2]，以下用表格標示每一步 two pointer 的位置（i為綠色，j/k為紅色）：

步驟	陣列狀態	指針位置	操作說明
Step 1	[-4, -1, -1, 0, 1, 2]	i=0, j=1, k=5	固定i=0(-4)，j=1(-1)，k=5(2)，sum=-3<0，j++
Step 2	[-4, -1, -1, 0, 1, 2]	i=0, j=2, k=5	sum=-3<0，j++
Step 3	[-4, -1, -1, 0, 1, 2]	i=0, j=3, k=5	sum=-2<0，j++
Step 4	[-4, -1, -1, 0, 1, 2]	i=0, j=4, k=5	sum=-1<0，j++
Step 5	[-4, -1, -1, 0, 1, 2]	i=0, j=5, k=5	j==k，i++，進入下一輪
Step 6	[-4, -1, -1, 0, 1, 2]	i=1, j=2, k=5	固定i=1(-1)，j=2(-1)，k=5(2)，sum=0，找到一組[-1,-1,2]，j++
Step 7	[-4, -1, -1, 0, 1, 2]	i=1, j=3, k=5	sum=0，找到一組[-1,0,1]，j++
Step 8	[-4, -1, -1, 0, 1, 2]	i=1, j=4, k=3	j>=k，i++，進入下一輪
Step 9	[-4, -1, -1, 0, 2, 1]	i=2, j=3, k=5	i=2(-1)與前一個重複，跳過
Step 10	[-4, -1, -1, 0, 1, 2]	i=3, j=4, k=5	固定i=3(0)，j=4(1)，k=5(2)，sum=3>0，k--
Step 11	[-4, -1, -1, 0, 1, 2]	i=3, j=4, k=4	j==k，結束

完整程式碼
#

java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>(); // 初始化結果列表
        Arrays.sort(nums); // 對陣列進行排序
        
        for(int i = 0; i < nums.length; i++) { // 遍歷陣列，固定第一個數字
            if(i > 0 && nums[i] == nums[i-1]) { // 跳過重複的第一個數字
                continue;
            }
            
            int j = i + 1; // 左指針從 i+1 開始
            int k = nums.length - 1; // 右指針從陣列結尾開始
            
            while(j < k) { // 當左右指針未相遇時繼續
                int sum = nums[i] + nums[j] + nums[k]; // 計算三數之和
                
                if(sum == 0) { // 如果和為零
                    res.add(Arrays.asList(nums[i], nums[j], nums[k])); // 加入結果
                    j++; // 移動左指針
                    
                    while(nums[j] == nums[j-1] && j < k) { // 跳過重複的左指針元素
                        j++;
                    }
                } else if(sum > 0) { // 如果和大於零
                    k--; // 移動右指針
                } else { // 如果和小於零
                    j++; // 移動左指針
                }
            }
        }
        
        return res; // 返回結果
    }
}