在演算法的世界裡，解題不僅僅是為了得到結果，更是如何在高效且優雅的方式中解決問題。今天我們要探討的是經典的 Leetcode 題目——三數之和。這道題考驗我們如何在複雜的數組中，不重複地找出和為 0 的三個數，並且同時兼顧演算法的時間複雜度。

在本文中，我將帶你了解如何透過排序與雙指針技術，在不犧牲效能的前提下解決這個問題。這不僅會讓你對數組處理有更深的理解，還能幫助你掌握在面對類似題型時應對自如的策略。準備好了嗎？讓我們一起進入「三數之和」的挑戰吧！

3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

題目描述

給定一個整數數組 nums，要求找出所有的三元組 [nums[i], nums[j], nums[k]]，使得 i != j、i != k 且 j != k，並且 nums[i] + nums[j] + nums[k] == 0。

請注意，解答集必須不包含重複的三元組。

實作：

function threeSum(nums: number[]): number[][] {
    nums.sort((a, b) => a - b); // 排序數組
    const res: number[][] = [];

    for (let i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue; // 避免重複的三元組
        }
        let left = i + 1;
        let right = nums.length - 1;

        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];

            if (sum === 0) {
                res.push([nums[i], nums[left], nums[right]]);

                // 移動左指針，避免重複
                while (left < right && nums[left] === nums[left + 1]) left++;
                left++;

                // 移動右指針，避免重複
                while (left < right && nums[right] === nums[right - 1]) right--;
                right--;
            } else if (sum < 0) {
                left++; // 和小於0，左指針右移
            } else {
                right--; // 和大於0，右指針左移
            }
        }
    }

    return res;
}

我們可以通過排序並使用雙指針技術來有效解決此問題。具體來說，我們先將數組進行升序排列，然後對每個數字 nums[i]，利用雙指針在 i 之後的部分進行查找，嘗試找到三元組。具體步驟如下：

1. 排序數組： 首先對數組進行排序，這樣可以讓我們方便地使用雙指針技術來進行查找。

2. 迴圈每一個數： 迴圈數組中的每一個元素，當前選定的數字是 nums[i]。為了避免重複的三元組，當 nums[i] 和前一個數相同時，可以跳過這次迴圈。

3. 雙指針查找： 對於每個 nums[i]，設置兩個指針 left 和 right，分別指向 i+1 和數組的末尾。通過計算 nums[i] + nums[left] + nums[right] 的和來判斷是否為 0：

   • 如果三數之和為 0，則將其加入結果集，並且需要移動 left 和 right，跳過重複的元素。
   • 如果三數之和小於 0，說明需要更大的數，因此移動 left 指針向右。
   • 如果三數之和大於 0，則說明需要更小的數，因此移動 right 指針向左。

4. 結束條件： 當指針相遇時，結束當前數字的查找，繼續下一個數字的遍歷。

解題脈絡：

• 這道題的核心在於如何在不產生重複的情況下找出所有的三元組，因此排序和跳過重複數字是解題的關鍵步驟。
• 利用雙指針法可以將時間複雜度降低至 O(n²)，相比於暴力解法的 O(n³)，這是一個較為高效的方法。

本次要點：

1. 排序和雙指針技巧： 排序可以幫助我們避免重複的解答，雙指針則能夠在 O(n²) 的時間內完成查找。
2. 跳過重複的元素： 使用 while 循環來跳過重複的數字，這樣可以保證結果集中不會有重複的三元組。
3. 結果集避免重複： 通過對數組進行排序並仔細管理指針的移動來避免結果集中出現重複的三元組。

總結來說，雙指標法是一種在排序數組中查找符合條件的元素組合的高效方法，尤其適合處理兩個或多個元素的和、差等問題。