題目鏈接：15. 三數之和

思路

排序 + 雙指針

采用 排序 + 雙指針 的方法來解決三數之和問題。首先對數組進行排序，然后通過雙指針法，針對每一個固定的元素，從其后的數組部分尋找符合條件的三元組。這樣能夠避免重復的三元組，且利用排序的性質來優化查找效率。

解題過程

方法運用

1. 排序數組：首先將數組 nums 進行升序排序，這樣可以方便使用雙指針法，同時也能跳過重復的元素，避免重復的三元組。
2. 遍歷數組：從第一個元素開始，依次固定一個數 nums[i]，然后使用雙指針法在 i+1 到數組末尾之間查找兩個數 nums[l] 和 nums[r]，使得三者之和為 0。
   • 如果三者之和等于 0，將該三元組加入結果集。
   • 如果三者之和小于 0，左指針右移以增大和。
   • 如果三者之和大于 0，右指針左移以減小和。
3. 跳過重復元素：為了避免重復的三元組，在遍歷過程中跳過相鄰相同的元素，并在更新指針時跳過重復的 nums[l] 和 nums[r]。

復雜度

• 時間復雜度: $O(n^2)$，排序的時間復雜度為 $O(n \log n)$，而雙指針的查找過程在最壞情況下為 $O(n^2)$，因此總的時間復雜度為 $O(n^2)$。
• 空間復雜度: $O(1)$，除了存儲結果的空間外，算法的空間開銷主要用于排序，排序可以在原數組上進行，因此不需要額外空間。

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 存儲結果的列表
        List<List<Integer>> res = new ArrayList<>();
        // 對數組進行排序
        Arrays.sort(nums);
        int n = nums.length;

        // 遍歷數組
        for (int i = 0; i < n - 2; i++) {
            // 跳過重復的第一個數字
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 雙指針查找
            int l = i + 1, r = n - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];

                if (sum == 0) {
                    // 找到三元組，加入結果集
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    
                    // 跳過重復的左邊元素
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    // 跳過重復的右邊元素
                    while (l < r && nums[r] == nums[r - 1]) r--;

                    // 移動雙指針
                    l++;
                    r--;
                } else if (sum < 0) {
                    l++;  // 左指針右移
                } else {
                    r--;  // 右指針左移
                }
            }
        }
        
        return res;
    }
}