首页 > 技术文章 > leetcode 15:3Sum

qingjiaowoxiaoxioashou 原文

描述:

  Given an array S of n integers,are there elements a,b,c in S such that a+b+c=0?find all unique triplets in the array which gives the sum of zero.

  Note:

  1.Element in a triplet(a,b,c) must be in non-descending order.(ie,a<=b<=c)

  2.The solution set must not contain duplicate triplets.

  For example,given array S={-1,0,1,2,-1,-4}.

  A solution set is:

  (-1,0,1)

  (-1,-1,2)

  分析:刚看到这个题的时候,就觉得这道题是TwoSum的升级版。。暴力求解法可以做,转化为查找的方法有点麻烦,因为这是三个数相加要等于零,三个数的平衡更难些,还有一个方法就是排序后左右夹逼。。注意这个题没有要求返回下标。

  由于暴力求解比较简单,所以在这里不详述了。下面我们就实现排序后左右夹逼的这种方法,时间复杂度为O(n2),类似的这个方法也可以求ksum

  代码如下:

推荐阅读