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

文章封面

截图未命名

一、题目解读

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

二、解题思路

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

三、解题步骤

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

  2. 外层循环固定首元素:遍历数组,每次固定第一个数(需跳过重复值)。

  3. 双指针搜索:

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

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

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

  1. 循环终止条件:确保左指针始终在右指针左侧,避免重复计算。

四、代码与注释

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)。关键在于利用有序数组的特性,通过首元素固定与双指针动态收缩区间,同时结合去重逻辑保证结果唯一性。适用于求解多元素和为定值的问题,是算法面试中的高频考点。

来源:力扣题解

评论

暂无评论