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

贾蔷
• 阅读 4

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

来源:力扣题解

点赞
收藏
评论区
推荐文章
BichonCode BichonCode
4年前
双指针问题
一、双指针之左右指针相关题目1.1题目要求:给定一个升序排列的整数数组,找到两个数,使它们的和等于给定的数,有且仅有一个满足条件的解,返回索引。题目分析:需要两个指针,一个指向开头,一个指向末尾,然后向中间遍历,如果指向的两个数相加正好等于target的话,直接返回两个指针的位置即可,若小于target,左指针右移一位,若大于target,右
贾蔷 贾蔷
2个月前
力扣1137题 解题思路和步骤 C++代码实现,力扣一共多少题
一、题目分析力扣1137题要求我们找到第N个泰波那契数。泰波那契数的定义是:T00,T11,T21,且在n0的条件下Tn3TnTn1Tn2。,当n4时,T4T3T2T14。这道题主要考查我们对递归或动态规划的理解和运用。在思考解题方法时,我们
贾蔷 贾蔷
1个月前
牛客12576题全解析:动态规划+质因数分解解决跳跃问题
一、题目解读牛客12576题是一道经典的算法题,要求给定起点N和终点M,求解从N到M的最少跳跃次数。题目考察的核心在于路径优化与动态规划思想,需结合数论中的质因数分解技巧,通过合理设计算法降低时间复杂度,避免暴力枚举的指数级耗时。二、解题思路采用“动态规划
深度学习 深度学习
1个月前
洛谷P2034题解:动态规划+单调队列优化求解最大K段子段和问题
一、题目解读洛谷P2034题目要求给定一个长度为n的整数数组,将其分成不超过k段,求各段和的最大值。该问题属于经典动态规划问题的扩展,需结合优化技巧高效求解。二、解题思路采用动态规划单调队列优化的策略。核心思想是定义状态dp
贾蔷 贾蔷
3星期前
牛客3750题滑动窗口最大值解析:双端队列优化解法与代码详解
一、题目解读要求在一个给定的整数中,计算固定大小为k的内元素的最大值。例如,当窗口滑动时,需要实时输出每个窗口中的最大值序列。该问题考察对的理解,以及如何高效维护窗口内的元素关系。二、解题思路采用(deque)维护的巧妙解法。核心思想是:中仅存储数组下标,
贾蔷 贾蔷
2星期前
2024蓝桥杯国赛B组最小字符串题解:贪心算法实战应用
一、题目解读题目要求给定一个长度为N的S和M个待插入字符,通过将这些字符全部插入S中,构造出最小的新字符串。这是典型的字符串构造问题,考察选手对的理解和应用能力。二、解题思路采用贪心策略:1.先将待插入字符,便于按字典序选择2.遍历原字符串时,在保证字典序
贾蔷 贾蔷
2星期前
【动态规划入门】力扣509题:斐波那契数列的经典解法与优化思路
一、题目解读‌是一个经典的数学问题,在计算机科学中常被用作教学的入门案例。这个神奇的数列从0和1开始,后续每个数字都是前两个数字之和。题目要求我们计算第n个,看似简单的问题背后却蕴含着重要的算法思想。当n较小时,这个问题似乎微不足道,但随着n的增大,不同的
贾蔷 贾蔷
1星期前
洛谷P1102题解:利用哈希表优化的数对统计 C++代码解析
一、题目解读P1102题要求处理一组整数与常数C,统计数组中是否存在元素A与B满足ABC。用户需输出满足条件的数对数量。题目关键在于快速判断是否存在互补元素,时间复杂度需优化以避免暴力遍历。二、解题思路采用(unorderedmap)实现高效统计。首先遍
深度学习 深度学习
1星期前
LeetCode 2576题解:双指针法求解最多标记下标(排序+贪心策略)
一、题目解读2576题要求在一个整数中寻找最多可标记的下标对:若nums法”的组合思路:1.排序预处理:对原数组nums进行升序排序,确保相同元素聚集,便于后续配对。2.双划分:将排序后的数组分为左右两半(左指针left0,右指针rightn/2),从
深度学习 深度学习
23小时前
洛谷P2758题解:动态规划求解编辑距离的完整攻略
一、题目解读P2758题要求计算两个之间的编辑距离,即通过插入、删除、替换三种操作将字符串A转换为B所需的最小操作次数。题目考察的核心是在中的应用,需要找到最优的路径。二、解题思路采用(DynamicProgramming)策略。核心思想是构建二维dp,d