三数之和算法详解：排序与双指针

题目

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

来源：15. 三数之和 - 力扣（LeetCode）

思路

核心思想：排序 + 双指针

为什么需要排序？

1. 有序数组才能使用双指针
2. 方便去重
3. 可以提前终止搜索

为什么用双指针？ 将 O(n³) 的暴力搜索优化为 O(n²)

复杂度

1. 排序阶段

• 使用快速排序或归并排序
• 时间复杂度：O(n log n)

2. 双指针搜索阶段

外层循环：执行 n-2 次，O(n) 内层循环：双指针，最坏 O(n) 总计：O(n × n) = O(n²)

为什么是 O(n²)？

• 固定 nums[i]，在 [i+1, n-1] 区间用双指针找两个数
• 双指针遍历区间长度平均为 n/2
• 所以是：n × (n/2) ≈ O(n²)

3. 总时间复杂度

O(n log n) + O(n²) = O(n²)

因为 n² 的增长速度比 n log n 快，所以主导项是 O(n²)。

4. 空间复杂度

排序：O(log n) 到 O(n)（取决于排序算法） 结果存储：O(k)，k 是结果数量 额外空间：O(1)（双指针只用常数空间） 总空间复杂度：O(n)（如果考虑结果存储） 如果不考虑结果存储：O(log n) 或 O(1)

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans; // 存储结果
        int n = nums.size(); // 数组长度
        // 1. 特殊情况处理：数组长度正好为 3
        if (n == 3) {
            int sum = nums[0] + nums[] + nums[];
             (sum == ) {
                ans.({nums[], nums[], nums[]});
            }
             ans; 
        }
        
        (nums.(), nums.());
        
         ( i = ; i < n; i++) {
            
            
             (i !=  && nums[i - ] == nums[i]) {
                ;
            }
            
             l = i + ; 
             r = n - ; 
            
             (l < r) {
                 sum = nums[i] + nums[l] + nums[r];
                 (sum > ) {
                    
                    r--;
                }   (sum < ) {
                    
                    l++;
                }  {
                    
                    ans.({nums[i], nums[l], nums[r]});
                    
                     (l < r && nums[l] == nums[l + ]) {
                        l++;
                    }
                    
                     (l < r && nums[r] == nums[r - ]) {
                        r--;
                    }
                    
                    l++;
                    r--;
                }
            }
        }
         ans;
    }
};