这篇文章主要讲解了“经典求和的问题有哪些”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“经典求和的问题有哪些”吧!
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
题目很容易理解,即让查看数组中有没有两个数的和为目标数,如果有的话则返回两数下标,在这为大家提供两种解法双指针(暴力)法,和哈希表法,大家可以看一下。
哈希表法
是不是很容易理解,下面我们来看一下题目代码。
双指针(L,R)法的思路很简单,L指针用来指向第一个值,R指针用来从L指针的后面查找数组中是否含有和L指针指向值的和为目标值的数。见下图
例:绿指针指向的值为3,蓝指针需要在绿指针的后面遍历查找是否含有 target - 3 的元素即 5 - 3 = 2,若含有返回即可。
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。 注意:答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为:[ [-1, 0, 1], [-1, -1, 2] ]
这个题目算是对刚才题目的升级,刚才题目我们是只需返回一个例子即可,但是这个题目是让我们返回所有情况,这个题目我们需要返回三个数相加为 0 的所有情况,但是我们需要去掉重复的三元组(算是该题的核心),所以这个题目还是挺有趣的,大家记得打卡呀。
我们这个题目的哈希表解法是很容易理解的,我们首先将数组排序,排序之后我们将排序过的元素存入哈希表中,然后我们首先通过两层遍历,确定好前两个数字,那么我们只需要哈希表是否存在符合情况的第三个数字即可,跟暴力解法的思路类似,很容易理解,但是这里我们需要注意的情况就是,例如我们的例子为[-2 , 1 , 1],如果我们完全按照以上思路来的话,则会出现两个解,[-2 , 1 , 1]和[1 , 1, -2]。具体原因为,确定 -2,1之后发现 1 在哈希表中,存入。确定 1 ,1 之后发现 -2 在哈希表中,存入。所以我们需要加入一个约束避免这种情况,那就是我们第三个数的索引大于第二个数时才存入。
上面这种情况时是不可以存入的,因为我们虽然在哈希表中找到了符合要求的值,但是 -2 的索引为 0 小于 2 所以不可以存入。
如果我们将上个题目的指针解法称做是双指针的话,那么这个题目用到的方法就是三指针,因为我们是三数之和嘛,一个指针对应一个数,下面我们看一下具体思路,其实原理很简单,我们先将数组排序,直接 Arrays.sort() 解决,排序之后处理起来就很容易了。下面我们来看下三个指针的初始位置。
初始情况见上图,我们看当前情况,三数之和为 -3 ,很显然不是 0 ,那么我们应该怎么做呢?
我们设想一下,我们当前的三数之和为 -3 < 0 那么我们如果移动橙色指针的话则会让我们的三数之和变的更小,因为我们的数组是有序的,所以我们移动橙色指针(蓝色不动)时和会变小,如果移动蓝色指针(橙色不动)的话,三数之和则会变大,所以这种情况则需要向右移动我们的蓝色指针,找到三数之和等于 0 的情况进行保存,如果三数之和大于 0 的话,则需要移动橙色指针,途中有三数之和为 0 的情况则保存。直至蓝橙两指针相遇跳出该次循环,然后我们的绿指针右移一步,继续执行上诉步骤。但是这里我们需要注意的一个细节就是,我们需要去除相同三元组的情况,我们看下面的例子。
这里我们发现 0 - 1 + 1 = 0,当前情况是符合的,所以我们需要存入该三元组,存入后,蓝色指针向后移动一步,橙色指针向前移动一步,我们发现仍为 0 -1 + 1 = 0 仍然符合,但是如果继续存入该三元组的话则不符合题意,所以我们需要去重。这里可以借助HashSet但是效率太差,不推荐。这里我们可以使用 while 循环将蓝色指针移动到不和刚才相同的位置,也就是直接移动到元素 0 上,橙色指针同样也是。则是下面这种情况,这样我们就实现了去重,然后继续判断当前三数之和是否为 0 。
动图解析:
给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。 注意: 答案中不可以包含重复的四元组。
示例:
给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。 满足要求的四元组集合为:[ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
我们已经完成了两数之和和三数之和,这个题目应该就手到擒来了,因为我们已经知道这类题目的解题框架,两数之和呢,我们就先固定第一个数 ,然后移动指针去找第二个符合的,三数之和,固定一个数,双指针去找符合情况的其他两位数,那么我们四数之和,也可以先固定两个数,然后利用双指针去找另外两位数。所以我们来搞定他吧。
三数之和是,我们首先确定一个数,然后利用双指针去找另外的两个数,我们在这个题目里面的解题思路是需要首先确定两个数然后利用双指针去找另外两个数,和三数之和思路基本一致很容易理解。我们具体思路可以参考下图。
这里需要注意的是,我们的 target 不再和三数之和一样为 0 ,target 是不固定的,所以解题思路不可以完全照搬上面的题目。另外这里也需要考虑去重的情况,思路和上题一致。
上图则为我们查找到一个符合条件的四元组的情况,查找成功之后,下一步移动蓝色指针,重新定义绿蓝指针,继续执行上面步骤。
动图解析:
感谢各位的阅读,以上就是“经典求和的问题有哪些”的内容了,经过本文的学习后,相信大家对经典求和的问题有哪些这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。