力扣15题三数之和解法（C++双指针算法详解）

一、题目解读

力扣15题（三数之和）要求在一个包含n个整数的数组中，找出所有三个数之和为0的组合，且每个组合的元素不能重复。题目考察数组遍历、排序算法与双指针技巧的结合，是经典的多指针问题，对时间复杂度优化有较高要求。

二、解题思路

采用“双指针”策略：首先对原数组排序，然后固定第一个数，通过左右指针在剩余区间内寻找和为目标的数对。核心逻辑在于利用排序后的有序性，通过双指针移动减少无效遍历，并跳过重复元素避免结果重复。

三、解题步骤

1. 排序预处理：对输入数组进行升序排序，为后续双指针操作奠定基础。

2. 外层循环固定首元素：遍历数组，每次固定第一个数（需跳过重复值）。

3. 双指针搜索：

○ 初始化左指针为i+1，右指针为数组末尾；

○ 计算当前三数之和，若为0则记录结果，并移动左右指针时需跳过重复元素；

○ 若和小于0，左指针右移扩大和值；若和大于0，右指针左移缩小和值。

4. 循环终止条件：确保左指针始终在右指针左侧，避免重复计算。

四、代码与注释

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        int n = nums.size();
        
        // 1. 排序预处理
        sort(nums.begin(), nums.end());
        
        // 2. 固定首元素遍历
        for (int i = 0; i < n - 2; ++i) {
            // 跳过重复首元素（优化）
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            int left = i + 1;     // 左指针
            int right = n - 1;    // 右指针
            int target = -nums[i]; // 目标值（三数和为0，即其余两数和为-target）
            
            // 3. 双指针搜索
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    // 找到有效组合
                    result.push_back({nums[i], nums[left], nums[right]});
                    // 跳过重复的left和right元素
                    while (left < right && nums[left] == nums[left + 1]) ++left;
                    while (left < right && nums[right] == nums[right - 1]) --right;
                    ++left;  // 移动指针
                    --right;
                } else if (sum < target) {
                    ++left;   // 和太小，右移左指针
                } else {
                    --right;  // 和太大，左移右指针
                }
            }
        }
        return result;
    }
};

注释说明：代码中通过排序降低复杂度，双指针动态调整搜索范围，并利用跳过重复元素避免冗余计算，确保结果正确且不重复。

五、总结

该解法通过排序和双指针技术将时间复杂度优化至O(n^2)，空间复杂度O(1)。关键在于利用有序数组的特性，通过首元素固定与双指针动态收缩区间，同时结合去重逻辑保证结果唯一性。适用于求解多元素和为定值的问题，是算法面试中的高频考点。