3sum java_15. 3Sum - 《Leetcode 前 300 题算法题解析（Java）》 - 书栈网 · BookStack

题目描述(中等难度)

解法一 暴力解法

无脑搜索，三层循环，遍历所有的情况。但需要注意的是，我们需要把重复的情况去除掉，就是 [1, -1 ,0] 和 [0, -1, 1] 是属于同一种情况的。

publicList>threeSum(int[]nums){

List>res=newArrayList>();

for(inti=0;i

for(intj=i+1;j

for(intk=j+1;k

if(nums[i]+nums[j]+nums[k]==0){

Listtemp=newArrayList();

temp.add(nums[i]);

temp.add(nums[j]);

temp.add(nums[k]);

//判断结果中是否已经有 temp 。

if(isInList(res,temp)){

continue;

}

res.add(temp);

}

}

}

returnres;

}

publicbooleanisInList(List>l,Lista){

for(inti=0;i

//判断两个 List 是否相同

if(isSame(l.get(i),a)){

returntrue;

}

}

returnfalse;

}

publicbooleanisSame(Lista,Listb){

intcount=0;

Collections.sort(a);

Collections.sort(b);

//排序后判断每个元素是否对应相等

for(inti=0;i

if(a.get(i)!=b.get(i)){

returnfalse;

}

}

returntrue;

}

时间复杂度：n 表示 num 的个数，三个循环 O(n³)，而 isInList 也需要 O(n)，总共就是

，leetCode 复杂度到了

一般就报超时错误了，所以算法还得优化。

空间复杂度：最坏情况，即 O(N), N 是指 n 个元素的排列组合个数，即

，用来保存结果。

解法二

参考了这里-Java-solution)

主要思想是，遍历数组，用 0 减去当前的数，作为 sum ，然后再找两个数使得和为 sum。

这样看来遍历需要 O(n)，再找两个数需要 O(n²)的复杂度，还是需要 O(n³)。

巧妙之处在于怎么找另外两个数。

最最优美的地方就是，首先将给定的 num 排序。

这样我们就可以用两个指针，一个指向头，一个指向尾，去找这两个数字，这样的话，找另外两个数时间复杂度就会从 O(n²)，降到 O(n)。

而怎么保证不加入重复的 list 呢？

要记得我们的 nums 已经有序了，所以只需要找到一组之后，当前指针要移到和当前元素不同的地方。其次在遍历数组的时候，如果和上个数字相同，也要继续后移。文字表述比较困难，可以先看下代码。

publicList>threeSum(int[]num){

Arrays.sort(num);//排序

List>res=newLinkedList<>();

for(inti=0;i

//为了保证不加入重复的 list,因为是有序的，所以如果和前一个元素相同，只需要继续后移就可以

if(i==0||(i>0&&num[i]!=num[i-1])){

//两个指针,并且头指针从i + 1开始，防止加入重复的元素

intlo=i+1,hi=num.length-1,sum=0-num[i];

while(lo

if(num[lo]+num[hi]==sum){

res.add(Arrays.asList(num[i],num[lo],num[hi]));

//元素相同要后移，防止加入重复的 list

while(lo

while(lo

lo++;hi--;

}elseif(num[lo]+num[hi]

elsehi--;

}

}

}

returnres;

}

时间复杂度：O(n²)，n 指的是 num

空间复杂度：O(N)，最坏情况，即 N 是指 n 个元素的排列组合个数，即

，用来保存结果。

总

对于遍历，这里用到了从两头同时遍历，从而降低了时间复杂度，很妙！

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情