http://梦破碎的地方!| LeetCode:15.三数之和
这道题如果用哈希法的话,思路和前面几道是差不多的,先把c放进map中,然后再a+b,同时去判断0-a-b是否存在在map中。但是这里题目要求要去重,其实这道题目使用哈希法并不十分合适,因为在去重的操作中有很多细节需要注意,在面试中很难直接写出没有bug的代码。
而且使用哈希法 在使用两层for循环的时候,能做的剪枝操作很有限,虽然时间复杂度是O(n^2),也是可以在leetcode上通过,但是程序的执行时间依然比较长 。
接下来介绍另一个解法:双指针法,这道题目使用双指针法 要比哈希法高效一些,那么来讲解一下具体实现的思路。
1、为什么要排序,如果不排序,例-2-14--1243-4,那么你a等于第一个-2时加入[-2,-2,4][-2,-1,3][-2,0,2],然后你后面如果还有-2那就可能重复[-2,-2,4][-2,-1,3][-2,0,2],那么你就得弄一个东西来存储这个-2表示a已经当过-2,以后每次a当个值就先判断它是不是等于-2,如果等于则continue,这样又要弄个容器放它每次a变化又要判断是否出现过,就比排序的麻烦,排序后,相等的肯定相连所以只需要判断nums[i]是否=nums[i-1]即可得出是否要continue,这就是排序的优势,所以先排序。
2、去重到底是去的是什么?是怎么去重的?去重时有什么要注意的?
如下已是排序状态-2-2-1-1011223344
对于a来说,如a=第一个-2,然后left=第二个-2,right=最后一个4,发现相加等于0,所以加入[-2,-2,4];然后继续leftright往中间移,left=第一个-1时,right=最后一个3时,发现相加等于0,舍友加入[-2,-1,3];然后继续leftright往中间移,left=0时,right=最后一个2时,发现相加等于0,结果加入[-2,0,2];
即当a=第一个-2时,所有-2+b+c=0的[-2,-2,4][-2,-1,3][-2,0,2]
都已经找过了,当a=第二个-2时,还有[-2,-1,3][-2,0,2],那么就重复了,所以当a=第二个-2的时候应该continue,所以当nums[i]=nums[i-1]时应该continue。
此时注意nums[i]=nums[i-1]和nums[i]=nums[i+1]是有区别的,如果用nums[i]=nums[i+1],如果此时nums只有[-1,-1,2]那a=第一个-1时,因为nums[i]=nums[i+1]所以continue即没有把[-1,-1,2]加入到结果中,那第二个-1时因为没有三个数了所以结束,所以结果为空,nums[i]=nums[i+1]就会导致这样的问题,所以应该用nums[i]=nums[i-1]而不是nums[i]=nums[i+1]
对于c即right来说,比如a=第一个-2,left=第二个-2,right=最后一个4,那么这是一个相加为0即[-2,-2,4];那right=倒数第二个4时,是不是还有一个[-2,-2,4],这是不是重复了,举个极端的例子-3111112222,left和right是不是每移一个就有一个[-3,1,2],所以此时left应该是,收获结果后即判断-3+最左边的1+最右边的2后发现等于0,然后先收获结果[-3,1,2]进结果集,然后去重让left把1走完一直移到和下一个不相等即111112的2这个位置,那此时应该是left[i]==left[i+1]时则让left往右移,还是left[i]==left[i-1]时则让left往右移?
这取决于你什么时候left++;right--;
如果是先left++;right--;再去重,则如下,
else{result.push_back(vector<int>{nums[i],nums[left],nums[right]});
left++;
right--;
while(left<right&&nums[left]==nums[left-1]){
left++;
}
while(left<right&&nums[right]==nums[right+1]){
right--;
}
}
如果是先去重再left++;right--;则如下,
else{result.push_back(vector<int>{nums[i],nums[left],nums[right]});
while(left<right&&nums[left]==nums[left+1]){
left++;
}
while(left<right&&nums[right]==nums[right-1]){
right--;
}
left++;
right--;
}
这是为啥?其实举个例子就很容易理解,比如-3-345
当a=-3,b=0,c=3时,收获结果进result后,你应该手动让left,right往中间各移一位,因为你代码只是三个数大于小于0时和去重时才移动leftright,那这个情况即没大于小于0时也没有好几个0,3,如果这时候不手动写个代码让他们移动那就卡在这里了,所以收获结果后left++,right--是肯定要了吧。
然后比如是这种情况-1-1-10122。
首先想清楚我们去重到底去什么,left=-1重复,去重即让left不再等于-1,而是等于-1的下一个0值。我们比如left去重-1即第二个-1已当过left,所以left已不再需要-1,即我们left去重后下一个应该是left=0,想通这一点是关键。
然后如果我们先去重再因为收获结果left++right--,那先去重那此时left=第二个-1,right=倒数第一个2,我们先只讨论left,那此时left怎样才能满足我们上面去重,此时如果用left[i]==left[i-1],那此时的left=-1就还等于left[i-1],所以left++,就一直到left=0,这样left就=0了开始你那个因为收获结果而手动left++right--的还没用上耶,再用上,那此时left又++就等于1了,显然不是我们想要的。如果此时用left[i]==left[i+1],那此时的left=第二个-1,left[i+1]=第三个-1,所以left++,继续此时的left=第三个-1,left[i+1]=0,不相等了,所以left不++,就还是停留在left=第三个-1,然后再因为收获而left++right--,最终left落在了0,就达到了去重的效果。
如果是先因为收获结果left++right--再去重,那先left++此时left=第三个-1,right=倒数第二个2,我们先只讨论left,那此时left怎样才能满足我们上面去重,此时如果用left[i]==left[i-1],那此时的left=-1就还等于left[i-1],所以left++,这样left就=0了就达到去重效果了。如果此时用left[i]==left[i+1],那此时的left=-1,left[i+1]=0,就因为不相等,那left就不++就还是=-1。
去重就是为了让left不再等于-1而是等于0,所以left[i-1]、left[i+1]其中哪个能去重就用哪个
right同理。
注意a去重是在获取结果之前,所以
要避免如果是[0,0,0,0,0]也能出现result={[0,0,0]},避免还没获取结果就去重完了啥也没获取。
3、双指针思路,让a从i=0开始去for循环nums,然后让i+1等于left,让最后一个为right,当nums[i]+nums[left]+nums[right]>0,因为是排序嘛,越右值越大,那现在三个数相加大于0,那就让right左移嘛,同理如果三个数<0则left右移,如果等于0就把这三个数的集合加入结果中。
双指针思路以前没见过三个变量的还可以用双指针,现在见过啦,思路不难,难的是怎么去重。
4、小细节
①去重的代码要在收获结果的代码后。
即while(right>left&&nums[right]==nums[right-1])right--;
while(right>left&&nums[left]==nums[left+1])left++;
要在if(nums[i]+nums[left]+nums[right]>0)right--;
elseif(nums[i]+nums[left]+nums[right]<0)left++;
else{result.push_back(vector{nums[i],nums[left],nums[right]});
的后面。
比如有这种情况[0,0,0,0,0],i=第一个0,left=第二个0,right=最后一个0,本该收获一个结果[0,0,0]的,如果你先去重再收获结果,那么先去重,因为都是0,所以left,right一直往中间移,到left=right了,就因为不符合循环条件left<right就出循环了,都还没收获到[0,0,0]就跳出循环结束了,这就错了,所以应该是先收获再去重。
②注意那些vector细节
怎么定义一个二维数组,vector<vector<int>>result;
怎么往二维数组中加数组,注意里面还有一个vector<int>{}。
result.push_back(vector<int>{nums[i],nums[left],nums[right]});
③注意-2-11234,当a走到1时,肯定出不了结果了,因为1和后面无论哪两个都不可能相加等于0因为都是正数了,所以当a走到大于0的值时,就应该直接返回result了
④既然三数之和可以使用双指针法,我们之前讲过的两数之和可不可以使用双指针法呢?如果不能,题意如何更改就可以使用双指针法呢?两数之和就不能使用双指针法,因为两数之和要求返回的是索引下标,而双指针法一定要排序,一旦排序之后原数组的索引就被改变了。
如果两数之和要求返回的是数值的话,就可以使用双指针法了。
5、-2-10023334567777
如代码的意思是三个数相加相等后才去重,你看代码去重的代码是在else(三个数相加=0)的{}内的。
意思是如上例-2,-1,3后,左边的那些3才在去重。那-2,-1,7的时候7那么多没有去重。
这是为什么?
如上例a=-2left=-1right=7,此时7也有很多相等为什么此时不去重7。
如果7时也去重,即意思就是right每左移一个,如果有相等的就去重,即每轮一次while(left<right)就if相等就去重。
但细想一下,这种去重其实对提升程序运行效率是没有帮助的。拿right去重为例,即使不加这个去重逻辑,依然根据while(right>left)和if(nums[i]+nums[left]+nums[right]>0)去完成right--的操作。多加了while(left<right&&nums[right]==nums[right+1])right--;这一行代码,其实就是把需要执行的逻辑提前执行了,但并没有减少判断的逻辑。最直白的思考过程,就是right还是一个数一个数的减下去的,所以在哪里减的都是一样的。所以这种去重是可以不加的。仅仅是把去重的逻辑提前了而已。
注意去重是为了什么?去重是为了避免出现重复的数组结果,去重还可以让leftright不断往中间移动。对于3来说,去重避免了重复的[-2,-1,3]同时使得right指针一直往左移至2。
但是对于7来说,它和a=-2和b没有相加等于0的,也就是说根本就不用担心出现重复的[a,b,c],那去重对7来说只是起到让right不断往左移的作用,不过前面就有了让right往左移的,即如果三个数相加大于0,那right就往左移,那此时再去重让它往左移就多此一举没必要,因为最终都会因为三个数相加大于0而左移完7的,你加这个去重,不过是提前在最后一个7的时候就先左移完7。
大致代码思路:
vector<vector<int>> result;sort(nums.begin(), nums.end());// 找出a + b + c = 0// a = nums[i], b = nums[left], c = nums[right]for (int i = 0; i < nums.size(); i++) {// 排序之后如果第一个元素已经大于零,那么无论如何组合都不可能凑成三元组,直接返回结果就可以了if (nums[i] > 0) {return result;}// 错误去重a方法,将会漏掉-1,-1,2 这种情况,即:if (nums[i] == nums[i + 1]) {continue;}// 正确去重a方法if (i > 0 && nums[i] == nums[i - 1]) {continue;}int left = i + 1;int right = nums.size() - 1;while (right > left) {// 去重复逻辑如果放在这里,0,0,0 的情况,可能直接导致 right<=left 了,从而漏掉了 0,0,0 这种三元组/*while (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;*/if (nums[i] + nums[left] + nums[right] > 0) right--;else if (nums[i] + nums[left] + nums[right] < 0) left++;else {result.push_back(vector<int>{nums[i], nums[left], nums[right]});// 去重逻辑应该放在找到一个三元组之后,对b 和 c去重while (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;// 找到答案时,双指针同时收缩right--;left++;}}}return result;
如果觉得《代码随想录--哈希表--三数相加题型》对你有帮助,请点赞、收藏,并留下你的观点哦!