【leetcode刷题】15. 3Sum

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

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • <center>#1 Two Sum</center> link Description:Given an arr...
    铛铛铛clark阅读 2,253评论 0 3
  • 动态规划 111. 爬楼梯思路类似斐波那契数列注意考虑第 0 阶的特殊情况 272. 爬楼梯 II思路类似上题,只...
    6默默Welsh阅读 2,485评论 0 1
  • 转载自:https://egoistk.github.io/2016/09/10/Java%E6%8E%92%E5...
    chad_it阅读 1,012评论 0 18
  • 《有的人》臧克家 ——纪念鲁迅有感 有的人活着 他已经死了; 有的人死了 他还活着。 有的人 骑在人民头上:“呵,...
    陌卿歆阅读 227评论 0 1
  • 今天下着小雨,我出门去吃早餐的时候还没下,上午十点多的时候下的小雨。都说春雨贵如油,这话一点也不假,初春正是花草生...
    干啥里阅读 362评论 0 1