今天给大家带来三道求和题。通过文字、图片、动画，为大家讲解。这很容易理解。每道题都是经典题，快来签到题源：leetcode1.两数之和（简单）15.三数之和（中）18.四数之和（中）两数之和题目描述：给定一个整数数组nums和一个目标值target，请在数组中找出和为目标值的两个整数，并返回它们的数组下标。您可以假设每个输入只有一个答案。但是，数组中的同一个元素不能使用两次。例子：给定nums=[2,7,11,15],target=9，因为nums[0]+nums[1]=2+7=9，所以很容易理解返回[0,1]的问题，也就是让查看数组中有没有两个数之和作为目标数？如果是，则返回这两个数字的下标。这里有两种解决方法：双指针（暴力）法和哈希表法。你可以看看。哈希表的方法很容易理解，我们只需要经过一个循环，如果我们的目标值是9，当前指针指向的值是2，我们只需要从哈希表中找出是否包含7，因为9-2=7。如果包含7，我们可以直接返回。如果不是，则将当前的2存入哈希表，并移动指针指向下一个元素。注：key为元素值，value为元素索引。动画解析：是不是很容易理解，我们来看片头代码。题代码：双指针（暴力）法思路分析双指针（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之后，发现hash表中存放的是1。1确定1后，发现-2在hash表中，存入。所以我们需要加一个约束来避免这种情况，就是只有当我们第三个数的索引大于第二个数的时候才存储。上面这种情况，是不能存储的，因为虽然我们在哈希表中找到了符合要求的值，但是-2的索引是0，小于2，所以不能存储。题码多指针分析：如果我们把上一题的指针解法称为双指针，那么这道题用的方法就是三指针，因为我们是三个数的和，一个指针对应一个数。下面我们来看看具体思路。其实原理很简单。我们先对数组进行排序，直接用Arrays.sort()来解决。排序后，处理起来就非常容易了。我们来看看三个指针的初始位置。初始情况如上图所示。让我们看看目前的情况。三个数之和为-3，显然不是0。那怎么办呢？假设我们当前三个数的和是-3<0。那么如果我们移动橙色指针会使我们三个数的和变小，因为我们的数组是有序的，所以当我们移动橙色指针（蓝色指针不动），总和会变小。如果我们移动蓝色指针（如果橙色不动），三个数之和就会变大，所以在这种情况下，我们需要将我们的蓝色指针向右移动，找到三个数之和的情况numbers等于0并保存。如果三数之和大于0，则需要移动橙色指针，如果途中三数之和为0，则保存。直到蓝色和橙色指针相遇跳出循环，这时我们的绿色指针向右移动一步继续上诉步骤。但是这里需要注意的一个细节是我们需要去掉相同的三元组。让我们看看下面的例子。这里我们发现0-1+1=0，目前的情况是一致的，所以我们需要存储三元组。存储后，蓝色指针向后移动一步，橙色指针向前移动一步。我们发现还是0-1+1=0还是符合的，但是如果继续存triplet，就不符合题意了，所以我们需要去重。这里可以使用HashSet，但是效率太差，不推荐。这里我们可以使用while循环将蓝色指针移动到和之前不一样的位置，即直接移动到元素0，橙色指针也是如此。就是下面这种情况，这样我们就实现了去重，然后继续判断当前三个数的和是否为0。target值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是不固定的，所以解题思路不能完全照搬上面的题。另外，这里还要考虑去重的情况，思路和前面的问题是一致的。上图是我们找到一个合格的四元组的情况。查找成功后，下一步就是移动蓝色指针，重新定义绿色和蓝色指针，继续执行上面的步骤。动画解析：话题代码：四个数之和转载本文请联系元初算法之家公众号。
