【算法专题--双指针算法】leecode-15.三数之和(medium)、leecode-18. 四数之和(medium)

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


【算法专题--双指针算法】leecode-15.三数之和(medium)、leecode-18. 四数之和(medium),算法,c++
🍁你好,我是 RO-BERRY
📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识
🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油

【算法专题--双指针算法】leecode-15.三数之和(medium)、leecode-18. 四数之和(medium),算法,c++



前言

双指针
常见的双指针有两种形式,一种是对撞指针,⼀种是左右指针。
对撞指针:一般用于顺序结构中,也称左右指针。

  • 对撞指针从两端向中间移动。一个指针从最左端开始,另⼀个从最右端开始,然后逐渐往中间逼近。
  • 对撞指针的终止条件一般是两个指针相遇或者错开(也可能在循环内部找到结果直接跳出循环),也就是:
    • left == right (两个指针指向同一个位置)
    • left > right (两个指针错开)

快慢指针:又称为龟兔赛跑算法,其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。
这种方法对于处理环形链表或数组非常有用。
其实不单单是环形链表或者是数组,如果我们要研究的问题出现循环往复的情况时,均可考虑使用快慢指针的思想。

快慢指针的实现方式有很多种,最常用的⼀种就是:

  • 在一次循环中,每次让慢的指针向后移动一位,而快的指针往后移动两位,实现一快一慢。

1. 三数之和

题目描述:

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。

示例 2:

输入:nums = [0,1,1]
输出:[ ]
解释:唯一可能的三元组和不为 0 。

示例 3:

输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。

提示:

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

2. 解法(排序+双指针):

算法思路:

本题与两数之和类似,是非常经典的面试题。
与两数之和稍微不同的是,题目中要求找到所有「不重复」的三元组。那我们可以利用在两数之和那里用的双指针思想,来对我们的暴力枚举做优化:

  1. 先排序;
  2. 然后固定⼀个数 a :
  3. 在这个数后面的区间内,使用「双指针算法」快速找到两个数之和等于 -a 即可。

但是要注意的是,这道题里面需要有「去重」操作~

  1. 找到⼀个结果之后, left 和 right 指针要「跳过重复」的元素;
  2. 当使用完⼀次双指针算法之后,固定的 a 也要「跳过重复」的元素

算法流程:

先将 nums 排序,时间复杂度为 O(NlogN)。

固定 333 个指针中最左(最小)元素的指针 k,双指针 i,j 分设在数组索引 (k,len(nums))(k, len(nums))(k,len(nums)) 两端。

双指针 iii , jjj 交替向中间移动,记录对于每个固定指针 k 的所有满足 nums[k] + nums[i] + nums[j] == 0 的 i,j 组合:

  1. nums[k] > 0 时直接break跳出:因为 nums[j] >= nums[i] >= nums[k] > 0,即 3 个元素都大于 0 ,在此固定指针 k 之后不可能再找到结果了。
  2. k > 0nums[k] == nums[k - 1]时即跳过此元素nums[k]:因为已经将 nums[k - 1] 的所有组合加入到结果中,本次双指针搜索只会得到重复组合。
    3.i,j分设在数组索引 (k,len(nums))两端,当i < j时循环计算sum = nums[k] + nums[i] + nums[j],并按照以下规则执行双指针移动:
  • s < 0时,i += 1并跳过所有重复的nums[i]

  • s > 0时,j -= 1并跳过所有重复的nums[j]

  • s == 0时,记录组合[k, i, j]至res,执行i += 1j -= 1并跳过所有重复的nums[i]nums[j],防止记录到重复组合。

C++代码:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        // 1. 排序
        sort(nums.begin(), nums.end());
        // 2. 利⽤双指针解决问题
        int n = nums.size();
        for (int i = 0; i < n;) // 固定数 a
        {
            if (nums[i] > 0) break; // ⼩优化
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right) 
            {
                int sum = nums[left] + nums[right];
                if (sum > target) right--;
                else if (sum < target) left++;
                else 
                {
                    ret.push_back({nums[i], nums[left], nums[right]});
                    left++, right--;
                    // 去重操作 left 和 right
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            // 去重 i
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};

【算法专题--双指针算法】leecode-15.三数之和(medium)、leecode-18. 四数之和(medium),算法,c++
Java代码:

class Solution
{
    public List<List<Integer>> threeSum(int[] nums)
    {
        List<List<Integer>> ret = new ArrayList<>();
        // 1. 排序
        Arrays.sort(nums);
        // 2. 利⽤双指针解决问题
        int n = nums.length;
        for (int i = 0; i < n; ) // 固定数 a
        {
            if (nums[i] > 0) break; // ⼩优化
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum > target) right--;
                else if (sum < target) left++;
                else
                {
                    // nums[i] nums[left] num[right]
                     ret.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[left], nums[right])));
                     left++; right--; // 缩⼩区间继续寻找
                     // 去重:left right
                     while (left < right && nums[left] == nums[left - 1]) left++;
                     while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            // 去重:i
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
}

【算法专题--双指针算法】leecode-15.三数之和(medium)、leecode-18. 四数之和(medium),算法,c++

3. 四数之和(medium)

题目描述:

给你一个由 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
    你可以按 任意顺序 返回答案 。

示例 1:

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

示例 2:

输入:nums = [2,2,2,2,2], target = 8
输出:[[2,2,2,2]]

提示:

1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

4. 解法(排序 + 双指针)

前置题目:
请先完成三数之和。

思路:
思路和三数之和 一样,排序后,枚举 nums[a]作为第一个数,枚举 nums[b] 作为第二个数,那么问题变成找到另外两个数,使得这四个数的和等于 target,这可以用双指针解决。
对于 nums[a] 的枚举:

  1. 设 s=nums[a]+nums[a+1]+nums[a+2]+nums[a+3]。如果 s>targets,由于数组已经排序,后面无论怎么选,选出的四个数的和不会比 s 还小,所以后面不会找到等于 target的四数之和了。所以只要 s>targets ,就可以直接 break 外层循环了。

  2. 设 s=nums[a]+nums[n−3]+nums[n−2]+nums[n−1]。如果 s<targets ,由于数组已经排序,nums[a]加上后面任意三个数都不会超过 s,所以无法在后面找到另外三个数与 nums[a]相加等于 target。但是后面还有更大的 nums[a],可能出现四数之和等于 target 的情况,所以还需要继续枚举,continue 外层循环。

  3. 如果 a>0且 nums[a]=nums[a−1],那么 nums[a] 和后面数字相加的结果,必然在之前算出过,所以无需执行后续代码,直接 continue 外层循环。(可以放在循环开头判断。)

对于 nums[b] 的枚举(b 从 a+1 开始),也同样有类似优化:

  1. 设 s=nums[a]+nums[b]+nums[b+1]+nums[b+2]。如果 s>targets,由于数组已经排序,后面无论怎么选,选出的四个数的和不会比 s 还小,所以后面不会找到等于 target 的四数之和了。所以只要 s>targets ,就可以直接 break。

  2. 设 s=nums[a]+nums[b]+nums[n−2]+nums[n−1]。如果 s<targets,由于数组已经排序,nums[a]+nums[b] 加上后面任意两个数都不会超过 s,所以无法在后面找到另外两个数与 nums[a] 和 nums[b] 相加等于 target。但是后面还有更大的 nums[b],可能出现四数之和等于 target 的情况,所以还需要继续枚举,continue。

  3. 如果 b>a+1b>a+1b>a+1 且 nums[b]=nums[b−1],那么 nums[b]\textit{nums}[b]nums[b] 和后面数字相加的结果,必然在之前算出过,所以无需执行后续代码,直接 continue。注意这里 b>a+1 的判断是必须的,如果不判断,对于示例 2 这样的数据,会直接 continue,漏掉符合要求的答案。

对于 Java/C++ 等语言,注意相加结果可能会超过 32 位整数范围,需要用 64 位整数存储四数之和。

思路来自灵茶山艾府

C++代码:

class Solution
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        vector<vector<int>> ret;
        // 1. 排序
        sort(nums.begin(), nums.end());
        // 2. 利⽤双指针解决问题
        int n = nums.size();
        for (int i = 0; i < n; ) // 固定数 a
        {
            // 利⽤ 三数之和
            for (int j = i + 1; j < n; ) // 固定数 b
            {
                // 双指针
                int left = j + 1, right = n - 1;
                long long aim = (long long)target - nums[i] - nums[j];
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum < aim) left++;
                    else if (sum > aim) right--;
                    else
                    {
                        ret.push_back({ nums[i], nums[j], nums[left++],
                       nums[right--] });
                        // 去重⼀
                        while (left < right && nums[left] == nums[left - 1])
                            left++;
                        while (left < right && nums[right] == nums[right + 1])
                            right--;
                    }
                }
                // 去重⼆
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            // 去重三
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};

【算法专题--双指针算法】leecode-15.三数之和(medium)、leecode-18. 四数之和(medium),算法,c++
Java代码:

class Solution
{
    public List<List<Integer>> fourSum(int[] nums, int target)
    {
        List<List<Integer>> ret = new ArrayList<>();
        // 1. 排序
        Arrays.sort(nums);
        // 2. 利⽤双指针解决问题
        int n = nums.length;
        for (int i = 0; i < n; ) // 固定数 a
        {
            // 三数之和
            for (int j = i + 1; j < n; ) // 固定数 b
            {
                // 双指针
                int left = j + 1, right = n - 1;
                long aim = (long)target - nums[i] - nums[j];
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum > aim) right--;
                    else if (sum < aim) left++;
                    else
                    {
                        ret.add(Arrays.asList(nums[i], nums[j], nums[left++],
                            nums[right--]));
                        // 去重⼀
                        while (left < right && nums[left] == nums[left - 1])
                            left++;
                        while (left < right && nums[right] == nums[right + 1])
                            right--;
                    }
                }
                // 去重⼆
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            // 去重三
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
}

【算法专题--双指针算法】leecode-15.三数之和(medium)、leecode-18. 四数之和(medium),算法,c++文章来源地址https://www.toymoban.com/news/detail-845164.html

到了这里,关于【算法专题--双指针算法】leecode-15.三数之和(medium)、leecode-18. 四数之和(medium)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 代码随想录-哈希表02 第454题.四数相加II&383. 赎金信&第15题. 三数之和&第18题. 四数之和

    第454题.四数相加II 第454题.四数相加II 条件:四个数组中分别取一个,相加和为0,求满足条件的元组个数 思路使用1个map,mapA保存 s1 s2中相加和及其出现次数 遍历s3 s4,去判断是否满足 0 - (s3[i] + s4[j]) 在mapA中,并统计出现次数 383. 赎金信 383. 赎金信 题目要求,s1 是否能由s

    2024年02月12日
    浏览(44)
  • 【算法专题--双指针算法】leecode-202. 快乐数(medium)、leecode-11. 盛最多水的容器(medium)

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 双指针 常见的双指针有两种形式,一种是对撞指针,⼀种是左右指针。 对撞指针:一般用于顺序结构中

    2024年03月23日
    浏览(38)
  • [哈希专题]四数相加|赎金信|三数之和|四数之和

    此题思路:前两个数求和sum,sum1=0-后两数之和。判断sum1是否在之前出现过,此时用到哈希表,即判断sum1是否在前两个数中出现过。从而求得个数。 此题思路:定义两个指针left和right,遍历i,看三个位置的值是否为0。如果三个点值大于0,right--;如果小于0,left++。等于零即

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

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

    2024年02月09日
    浏览(37)
  • 【算法专题突破】双指针 - 三数之和(7)

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后: 题目链接:15. 三数之和 - 力扣(Leetcode)  题目就是要找出和为0的不重复的三元组, 注意三元组的每个元素是得不同的位置,那不重复又是什么意思呢? 我们可以看第一个示例, 他找出了三个三元组,但是他最后只返回

    2024年02月09日
    浏览(39)
  • 【leetcode】18. 四数之和(medium)

    给你一个由 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 你

    2024年02月13日
    浏览(43)
  • 【leetcode】15. 三数之和(medium)

    给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 你返回所有和为 0 且不重复的三元组。 注意:答案中不可以包含重复的三元组。 这题真的好难,试了好多方法,最后参考了代码随想录的

    2024年02月13日
    浏览(60)
  • 力扣精选算法100题——四数之和(双指针专题)

    上一篇讲到(俩数之和and三数之和)这一篇我要来解析四数之和,四数之和建立在三数之和的基础上,我们需要熟练掌握三数之和的算法原理,如果大家三数之和还没弄清楚,请点击三数之和and二数之和链接即可看到。  三数之和和四数之和的题意其实都一样。 找到出四个数

    2024年01月19日
    浏览(44)
  • 我在代码随想录|写代码Day7之454.四数相加II ,​ 383. 赎金信​,​ 15. 三数之和​

    题目  解题思路 四个数字相加的和为0,我们要选俩数组,让他们的笛卡尔积储存在哈希表中,然后我们要找的是这俩数和的相反数,然后就是将后面俩数组相加在后面的数组和中找相反数.   解题思路 题目意思是让在字符串1中找到字母组成字符串2所以找字符串1的数量.所以可以用

    2024年01月20日
    浏览(40)
  • (双指针 ) 18. 四数之和 ——【Leetcode每日一题】

    难度:中等 给你一个由 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

    2024年02月07日
    浏览(57)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包