题解 | 三数之和

class Solution {
  public:
    vector<vector<int>> threeSum(vector<int>& num) {
        vector<vector<int>> result;
        int n = num.size();
        if (n < 3) {
            return result;
        }

        // 先对数组进行排序
        sort(num.begin(), num.end());

        for (int i = 0; i < n - 2; i++) {
            // 跳过重复的固定数
            if (i > 0 && num[i] == num[i - 1]) {
                continue;
            }

            // 提前终止：如果当前固定的数已经大于0，由于数组已排序，后面的数都大于0
            // 三数之和不可能为0，直接结束循环
            if (num[i] > 0) {
                break;
            }

            int left = i + 1;
            int right = n - 1;
            int target = -num[i];  // 需要找到两个数之和等于 -num[i]

            while (left < right) {

                int current_sum = num[left] + num[right];

                if (current_sum == target) {
                    // 找到满足条件的三元组
                    result.push_back({num[i], num[left], num[right]});

                    // 跳过重复的左指针元素
                    while (left < right && num[left] == num[left + 1]) {
                        left++;
                    }
                    // 跳过重复的右指针元素
                    while (left < right && num[right] == num[right - 1]) {
                        right--;
                    }

                    // 移动指针寻找下一组
                    left++;
                    right--;
                } else if (current_sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return result;
    }
};

核心思路
排序：先对数组排序，这样可以使用双指针技巧
固定一个数：遍历数组，对于每个数 num[i]，在剩余部分寻找两个数使其和为 -num[i]
双指针：使用左右指针在排序后的数组中高效寻找匹配的数对
去重：在每一步都跳过重复元素，避免重复的三元组

时间复杂度
排序：O(n log n)
双指针遍历：O(n²)
总体：O(n²)

空间复杂度
结果存储：最坏情况 O(n²)，但实际中远小于这个值
排序：O(log n)（快速排序的栈空间）

关键优化点
提前终止：当固定的数 num[i] > 0 时，由于数组已排序，后面的数都大于0，三数之和不可能为0
去重处理：在三个位置都进行了去重：
固定数 num[i] 的去重
左指针 num[left] 的去重
右指针 num[right] 的去重