004-三数之和（双指针）

三数之和问题

三数之和（3Sum）是一个经典的算法问题，通常描述为：给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a, b, c，使得 a + b + c = 0？找出所有满足条件且不重复的三元组。

解决方案

方法一：排序 + 双指针

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function threeSum(nums) {
    // 1. 首先对数组进行排序
    nums.sort((a, b) => a - b);
    const result = [];
    const n = nums.length;
    
    // 2. 外层循环，固定第一个数
    for (let i = 0; i < n - 2; i++) {
        // 3. 跳过重复的第一个数
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        
        // 4. 初始化双指针
        let left = i + 1;
        let right = n - 1;
        
        // 5. 内层循环，使用双指针寻找另外两个数
        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            
            if (sum < 0) {
                // 6. 和太小，移动左指针增大和
                left++;
            } else if (sum > 0) {
                // 7. 和太大，移动右指针减小和
                right--;
            } else {
                // 8. 找到有效三元组
                result.push([nums[i], nums[left], nums[right]]);
                
                // 9. 跳过重复的left和right值
                while (left < right && nums[left] === nums[left + 1]) left++;
                while (left < right && nums[right] === nums[right - 1]) right--;
                
                // 10. 移动指针继续寻找
                left++;
                right--;
            }
        }
    }
    return result;
}
```

算法分析

1. 时间复杂度：O(n²) - 排序需要 O(n log n)，双指针遍历需要 O(n²)
2. 空间复杂度：O(1) 或 O(n) - 取决于排序算法的实现

关键点总结

1. 排序：使我们可以使用双指针技巧

2. 外层循环：固定第一个数nums[i]

3. 内层双指针：

   • left从i+1开始
   • right从数组末尾开始

4. 和的计算：

   • sum < 0 → 需要更大的数 → left++
   • sum > 0 → 需要更小的数 → right–
   • sum = 0 → 找到解

5. 跳过重复：确保结果中没有重复的三元组

通过这样一步步的图解，你应该能更清楚地理解三数之和的解法了。