【LeetCode系列】15.三数之和

1。题目描述给定一个包含n个整数的数组nums，判断nums中是否存在a,b,c三个元素，使得a+b+c=0？找出所有满足条件且不重复的三元组。示例：给定数组nums=[-1,0,1,2,-1,-4]，满足要求的三元组集合为：[[-1,0,1],[-1,-1,2]]2。题目分析这道题和LeetCode第二题两数之和的思路类似。上一篇文章已经详细解释了两个数字的总和。可以点击链接回顾【【LeetCode刷题系列】1.两数之和】（https://segmentfault.com/a/11....让我们简单回顾一下两数之和，求出两个数组中的元素，求和为目标值，即a+b=target。这道题的要求是a+b+c=0，我们可以稍微变换一下题目。根据换位，可以得到方程a+b=-c那么问题就转化为能否在数组中找到两个数使得它们的和等于另一个数的相反数这个时候这个数的相反数number是我们两个数之和中的target，不同的是这里的target不是固定的数，可能是数组中的每一个数注意：这道题要求找到所有满足条件的三元组和不重复。为了避免数组中相同元素对算法最终结果的影响，我们需要先对数组进行排序（中的排序算法在C++中可以使用），当然这道题的重点不在于如何排序，所以大家需要注意算法中的重复检查。一、暴力解根据前面的分析，我们可以知道，我们可以遍历数组中的每一个元素，并以其相反数作为目标。同时检查两个元素之和是否等于数组剩余元素中的target。同时在嵌套的第二层和第三层继续使用暴力解法，这样我们就进行了三层循环，算法的时间复杂度为$O(n^3)$.该算法思路简单，但最终时间复杂度比较大。有兴趣的朋友可以自己敲代码。二．我们有什么办法可以优化暴力破解的两指针法吗？什么？首先，在第一步中，我们需要遍历数组中的每一个元素，固定它，取其相反的数作为我们的目标值（target）。这一步O(n)的时间复杂度是我们不可避免的。那么在寻找剩余元素的过程中，我们可以做些什么来提高我们算法的时间复杂度呢？相信大家已经想到了，使用二数相加问题中讲解的哈希表方法，可以大大降低查找的时间复杂度。但在这里我想向大家介绍一种更自然、更通用、更容易理解的方法——双指针法。在使用双指针方法之前，大家要记住，我们需要对数组进行预处理，即对数组进行排序。当然，对于这道题，我们在前面的分析中已经对数组进行了排序。当我们开始遍历数组时，每当我们固定数组中的一个元素时，此时，将双指针j和k放在右数组的两端。如果指针取值的元素之和大于我们的目标，则将右指针向左移动；同理，如果元素之和小于我们的目标，就把左边的指针向右移动。就这样不断的把指针往中间移动（这有点像高等数学学的“钳位定理”），直到找到每一个满足条件的i,j,k值存入数组，并且最后它的回报。比如下图中的数组，当我们固定数组的第一个元素i=0时，将其相反的数字4作为我们的目标，指针j和k分别位于右边数组的两端，当当指针指向的值和-3+4=11，所以我们将右指针移动到一直向左直到找到-1+2=1时j和k的位置，最后设i,j,k一起返回。3.手绘讲解对数组进行排序，遍历数组中的每一个元素，然后使用双指针的方式进行查找。注意：为了避免数组中重复元素的影响，需要使用如下代码进行校验！