原题链接:https://leetcode.com/problems/3sum/
解题思路:
首先将数组进行排序,排序过后i对整个列表进行遍历,j从i+1开始遍历,k从最后一位往前遍历。要使三个数的sum为零,即
nums[i]+nums[j]+nums[k]=0
相当于使
nums[j]+nums[k]=-nums[i]
当nums[j]+nums[k] > nums[i] 时,说明需要减小nums[j]+nums[k],故将k向左移;
当nums[j]+nums[k] < nums[i] 时,说明需要增大nums[j]+nums[k],故将j向右移;
这个过程中如果nums[j]+nums[k] = nums[i],则让i增加1,并append此时的三个数。
其中两点值得注意:
1. i只需遍历到0,因为当i>0以后,无论如何三个数加起来都大于0了
2. 为避免结果中某一组合重复出现,当nums[i]=nums[i-1]时,i直接加1;当nums[j]=nums[j-1]时,j直接加1;当nums[k]=nums[k+1]时,k直接加1
代码参考:https://www.cnblogs.com/chruny/p/4820473.html
网友评论