【C++ leetcode】双指针(专题完结)

这篇具有很好参考价值的文章主要介绍了【C++ leetcode】双指针(专题完结)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【C++ leetcode】双指针(专题完结),leetcode,c++,算法

15. 三数之和

题目

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

题目链接

. - 力扣(LeetCode)

画图 和 文字 分析

这道题和 两数之和等于一个值 大体思路是一样的,都是 排序 + 双指针思想

排完序后,我们定义三个指针,一个指向最后一个元素的位置,一个指向首元素的位置,另一个首元素的后一个位置

举例:

输入: [-1,0,1,2,-1,-4]

输出:[[-1,-1,2],[-1,0,1]]

【C++ leetcode】双指针(专题完结),leetcode,c++,算法

先固定 k不动

  1. 如果三者指向的值相加为 0 ,则记录数据 ,再 j++ , k--
  2. 如果三者指向的值 < 0 ,则 j++
  3. 如果三者指向的值 > 0 ,则 k--

当 i >= j (结束里层循环)

再 i++ , j = i + 1 , k = n - 1

直到 i + 1 >= k (外层循环)

做到以上,只能说完成了完成了不漏掉每一种情况,但现在还有去重的关键一步

去重需要我们在前面的基础上做更改:

第一种情况:

走完上面的步骤 :

【C++ leetcode】双指针(专题完结),leetcode,c++,算法

判断现在 j 所指的内容 和 j - 1 所指内容是否相同,直到不相同为止(这里需要一个循环,此时要么,j 指向一个不和之前相重复的数,要么越界)

判断 k 同理

上面是里层循环的去重,外层循环也可以去重

当结束里层循环,完成后面的步骤 :

【C++ leetcode】双指针(专题完结),leetcode,c++,算法

判断 i 所指向的内容 和 i - 1所指向的内容是否相同,直到不相同为止

【C++ leetcode】双指针(专题完结),leetcode,c++,算法

【C++ leetcode】双指针(专题完结),leetcode,c++,算法

注意:

去重的时候,因为循环的缘故,一定要防止越界

 

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        vector<vector<int>> t;
        sort(nums.begin(),nums.end());
        int i = 0;
        while(i + 2 <= nums.size() - 1)
        {
            int j = i + 1;
            int k = nums.size() - 1;;
            while(j < k)
            {
                if(nums[i] + nums[j] + nums[k] > 0)
                {
                    k--;
                }
                else if(nums[i] + nums[j] + nums[k] < 0)
                {
                    j++;
                }
                else
                {
                    vector<int> x;
                    x.push_back(nums[i]);
                    x.push_back(nums[j]);
                    x.push_back(nums[k]);
                    t.push_back(x);
                    int n = nums[j];
                    int m = nums[k];
                    k--;
                    j++;
                    while(j < k && n == nums[j])
                    {
                        j++;
                    }
                    while(j < k && m == nums[k])
                    {
                        k--;
                    }
                }
            }
            int h = nums[i];
            i++;
            while(i + 2 <= nums.size() - 1 && h == nums[i])
            {
                i++;
            }
        }
        
        return t;
    }
};

18 . 四数之和

题目

给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

题目链接

. - 力扣(LeetCode)

画图 和 文字 分析

在 leetcode 15. 三数之和 基础之上做出的改变

思想:排序 + 双指针思想

定义四个指针,三个指针分别指向前三个元素的位置,第四个指针指向最后一个元素的位置

举例:

输入:nums = [1,0,-1,0,-2,2], target = 0

输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

后面的三个指针和之前的做法一模一样,第一个指针在里层所有循环结束后++

【C++ leetcode】双指针(专题完结),leetcode,c++,算法

再判断现在 a 所指向的元素和 a - 1 所指向的元素是否相同

直到 a + 2 >= d (外层循环结束)

【C++ leetcode】双指针(专题完结),leetcode,c++,算法

【C++ leetcode】双指针(专题完结),leetcode,c++,算法

【C++ leetcode】双指针(专题完结),leetcode,c++,算法

【C++ leetcode】双指针(专题完结),leetcode,c++,算法

注意:文章来源地址https://www.toymoban.com/news/detail-849555.html

  1. 注意越界情况
  2. 判断四数之和是否得到一个值,这里容易由于数据过大发生整型溢出现象,可以改成 longlong 类型 或者针对处理这一可能

代码

class Solution {
public:
    bool iscompare(int &a,int &b,int &c,int &d,int &target)
    {
         if(target < 0 && (a >= 0 && b >= 0 && c >= 0 && d >= 0))
         {
            return false;
         }
         else if(target > 0 && (a <= 0 && b <= 0 && c <= 0 && d <= 0))
         {
            return false;
         }
         else if(target == 0 && ((a > 0 && b > 0 && c > 0 && d > 0) || (a > 0 && b > 0 && c > 0 && d > 0)))
         {
            return false;
         }
         else
         {
            return true;
         }
    }
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        vector<vector<int>> s;
        int n = nums.size() - 1;
        sort(nums.begin(),nums.end());
        int a = 0;
        while(a + 2 < n)
        {
            int b = a + 1;
            while(b + 1 < n)
            {
                
                int  c = b + 1;
                int  d = n;
                while(c < d)
                {
                    if(!iscompare(nums[a],nums[b],nums[c],nums[d],target))
                    {
                        break;
                    }
                    if(nums[a] + nums[b]  > target - nums[c] - nums[d] )
                    {
                        d--;
                    }
                    else if(nums[a] + nums[b]  < target - nums[c] - nums[d] )
                    {
                        c++;
                    }
                    else
                    {
                        vector<int> t;
                        t.push_back(nums[a]);
                        t.push_back(nums[b]);
                        t.push_back(nums[c]);
                        t.push_back(nums[d]);
                        s.push_back(t);
                        int s1 = nums[c];
                        int s2 = nums[d];
                        d--;
                        c++;
                        while(c < d && nums[c] == s1)
                        {
                            c++;
                        }
                        while(c < d && nums[d] == s1)
                        {
                            d--;
                        }

                    }
                }
                int s3 = nums[b];
                b++;
                while(b + 1 < n && nums[b] == s3)
                {
                   b++;
                }
            }
            int s4 = nums[a];
            a++;
            while(a + 2 < n && nums[a] == s4)
            {
                a++;
            }
        }
        return s;
    }
};

到了这里,关于【C++ leetcode】双指针(专题完结)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法专题】双指针

    常见的双指针有两种形式,⼀种是对撞指针,⼀种是左右指针。 对撞指针:⼀般用于顺序结构中,也称左右指针。 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。 对撞指针的终止条件⼀般是两个指针相遇或者错开(也可能

    2024年02月05日
    浏览(33)
  • 双指针算法专题

    双指针算法入门,干就完了 下面的题目都是来自灵神的基础算法精讲,有思路不清晰的地方,可以去看讲解。 灵茶山艾府的个人空间-灵茶山艾府个人主页-哔哩哔哩视频 (bilibili.com) 题目链接:167. 两数之和 II - 输入有序数组 - 力扣(LeetCode) 题目描述 给你一个下标从 1 开始

    2024年01月23日
    浏览(45)
  • 【算法优选】双指针专题——壹

    常⻅的双指针有两种形式,⼀种是 对撞指针 ,⼀种是 左右指针 对撞指针 :⼀般⽤于顺序结构中,也称左右指针。 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。 对撞指针的终⽌条件⼀般是两个指针相遇或者错开(也可能

    2024年02月08日
    浏览(46)
  • 【算法优选】双指针专题——叁

    常⻅的双指针有两种形式,⼀种是 对撞指针 ,⼀种是 左右指针 对撞指针 :⼀般⽤于顺序结构中,也称左右指针。 对撞指针从两端向中间移动。⼀个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。 对撞指针的终⽌条件⼀般是两个指针相遇或者错开(也可能

    2024年02月08日
    浏览(45)
  • 【算法专题突破】双指针 - 移动零(1)

    目录 写在前面 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 在进行了剑指Offer和LeetCode hot100的毒打之后, 我决心系统地学习一些经典算法,增强我的综合算法能力。 题目链接:283. 移动零 - 力扣(Leetcode) 读完题目大概就能明白他的意思, 就是在不改变其他数字的情况下

    2024年02月11日
    浏览(37)
  • 【算法专题突破】双指针 - 快乐数(3)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:202. 快乐数 - 力扣(Leetcode) 这道题的题目也很容易理解, 看一下题目给的示例就能很容易明白, 但是要注意一个点,最后有可能无限循环无法到达1。 这个时候我们就要想一下怎么判断他是无线循环呢? 实际

    2024年02月11日
    浏览(32)
  • 【优选算法】专题1 -- 双指针 -- 复写0

    前言: 补充一下前文没有写到的双指针入门知识:专题1 -- 双指针 -- 移动零 目录 基础入门知识: 1. 复写零(easy) 1. 题⽬链接:1089.复习0 - 力扣(LeetCode) 2. 题⽬描述: 3.算法原理: 异地操作 本地操作 【从后向前的复写过程】 整体思路: 🎯1.先找到最后一个“复写”的

    2024年04月17日
    浏览(32)
  • 【算法专题突破】双指针 - 复写零(2)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:1089. 复写零 - 力扣(Leetcode) 我先来读题, 题目的意思非常的简单,其实就是, 遇到 0 就复制一个写进数组,然后右边的元素就右移一位, 看一眼例子可以很容易理解题意。  一般像这种需要移动数组的元素

    2024年02月11日
    浏览(45)
  • 【算法专题】双指针—盛最多水的容器

      分析这个题目不难得出一个 容积公式   解法一:暴力枚举(超时) 套用上述的容积公式,使用 两个for循环 来枚举出所有可能的情况,再挑出最大值即可,但是这种写法会超时,导致不通过。时间复杂度是O(n^2) 可以自己去尝试一下。  解法二:双指针  设两个指针 left,

    2024年02月06日
    浏览(49)
  • 【算法专题突破】双指针 - 四数之和(8)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:18. 四数之和 - 力扣(Leetcode)  这道题跟三数之和也是一样的, 题目很好理解,就是四个数的和等于target的情况, 且这四个数不能重复。 首先还是暴力解法: 排序 + 暴力枚举 + set去重 我们当然是用优化的解法

    2024年02月09日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包