美文网首页
【leetcode刷题】15. 3Sum

【leetcode刷题】15. 3Sum

作者: maodoudou168 | 来源:发表于2019-03-19 15:52 被阅读0次

    原题链接: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

    相关文章

      网友评论

          本文标题:【leetcode刷题】15. 3Sum

          本文链接:https://www.haomeiwen.com/subject/xyzgmqtx.html