题目意思 :
在一个数组中,无重复元素,找出所有 组合 他们的和 == 0 即 a + b + c = 0;
组合满足的条件 :
1 . a < b < c
2 . 组合不能重复
题目思路:
如果是暴力求解话,那么就得有三个for循环,时间复杂度为 O(n^3);
而下面的方法,为O(n^2)
首先对数组排序;
然后可以借鉴暴力求解的方法;
比如说,对数组 - 1 ,0, 1, 2 ;
当 i = -1 , j = 0 , 看k = 1 或 者 k = 2 是否满足条件
然后就是 i = -1 , j= 1 , 看 k = 2 是否满足条件
这里我们就可以得出一条结论:i+j 搭配,j后的元素只可能存在一个k 使得i+j+k = 0 (数组排好序,而且无重复元素)
如果i + j + k > 0 那么 k 之后的与 i + j 相加也必然 > 0 , 所以,此时,只能使 j , k 某个 减小 才能使得 i + j + k == 0 , 所以 k--;
同理i + j + k < 0 因为k 是往前移的,所以只能j++,才有可能 === 0;
好的算法,不会做无意义的重复的事情;
就拿这个方法与暴力方法比较;
对于 -1 , 0 ,1 ,2 ,3 , 4
暴力 : i = -1 , j = 0 , k = 1 , i + j + k == 0 , 明显对于 i = -1 , j = 0 的情况,不可能再有其他的元素使得i+j+k=0,所以接下来的k = 2 , k = 3 ,
是完全没有必要的操作,但是暴力方法,仍然在傻乎乎的计算,所以就慢了;
但是对于运用前后指针的方法,就不会这么傻乎乎的了,当i + j + k == 0 , 它知道对于i+j 这种情况不可能再有别的结果了,所以j++;
那么此时 i+j + k 必然 > 0 , 所以 , k--; 再计算,不就成功跳过了那些没意义的操作了吗?
实现代码 (来自DISCUSS)
public class Solution { // 三个数的和为0 看下面这种让人叹为观止的方法 // 前后指针的妙处! // excellent public List<List<Integer>> threeSum(int[] arr) { List<List<Integer>>lists = new ArrayList<List<Integer>> (); HashSet<List<Integer>> set = new HashSet<> (); int len = arr.length; if(len < 3) return lists; Arrays.sort(arr); for(int i = 0 ; i < len - 2; i++) { // 定义前后指针 for(int j = i + 1 , k = len - 1; j < k ; ) { int count = arr[i] + arr[j] + arr[k]; // (i+j) 相对k 太大 if(count < 0) j++; else if(count > 0) k--; else { List<Integer> list = new ArrayList<> (); list.add(arr[i]); list.add(arr[j]); list.add(arr[k]); if(set.add(list)) lists.add(list); // 这里如果是contains就不行了,因为他会遍历这个数组进行比较 // if(!lists.contains(list)) lists.add(list); // 对于(i + j)来说,只可能存在一个k使得他们 == 0 (无重复元素) j++; k--; } } } return lists; } }
其实我第一想法,是hash , 数组排序,然后遍历一边数组,把每一个元素的相反数作为key 放入,map,
那么两层for循环遍历数组,找到所以的两个元素的组合,看他们的和是否在map,如果在,再
进行相应的重复检查,放入lists中
无奈超时了..........
相关推荐
函数指针数组的妙用,妙用函数指针!
c语言c语言c语言c语言c语言c语言c语言指针的妙用c语言指针的妙用c语言指针的妙用
双指针算法,python数组双指针算法求和问题LeetCode2sum3sum4sum含代码
文档python数组双指针算法求和问题LeetCode2sum3sum4sum含代码提取方式是百度网盘分享地址
非常漂亮水晶鼠标指针 非常漂亮水晶鼠标指针 3D 水晶 鼠标
在阅读源码的过程中,我发现很多的代码中都采用了链表,链表的也是非常有意义的一种。有我们在C语言中使用的那种数据嵌套指针的方式。也有在linux中将链表作为一个单独的对象,然后将这...这些方式都是常用的方式之一。
彻底理解指针,指针数组和数组指针,指针函数和函数指针.doc
3D锥形动态鼠标指针point blue & black 三种颜色 超酷 本人喜欢黑色的
鼠标指针下载鼠标指针下载鼠标指针下载鼠标指针下载鼠标指针下载鼠标指针下载鼠标指针下载鼠标指针下载鼠标指针下载鼠标指针下载Yangcong WolfYangcong WolfYangcong WolfYangcong WolfYangcong WolfYangcong ...
C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针C指针
c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针c语言指针...
指针 指针教程 指针练习指针 指针教程 指针练习
那么是错误的,因为编译器会返回一个无法将char* *[3]转换给char *的错误,b=a的赋值,实际上是把a的首地址赋给了b,由于b是一个指向指针的指针,程序的输出cout*b|"*(b+1)|"*(b+2); 结果是 abc cde fgh 可以看出每...
vc+ 用指针实现二维数组的转置,通过指针实现对二维数组的转置操作
void指针void指针void指针void指针void指针
10.7 指针数组和指向指针的指针 10.7.1 指针数组的概念 一个数组的元素值为指针则是指针数组。 指针数组是一组有序的指针的集合。 指针数组的所有元素都必须是具有相同存储类型和指向相同数据类型的指针变量。 指针...
3D动态旋转鼠标指针 3D动态旋转鼠标3D动态旋转鼠标指针指针
指针精通指针精通指针精通指针精通指针精通指针精通指针精通指针精通指针精通指针精通指针精通指针精通
我知道函数指针是指向函数的指针,指针函数还是指一个函数的返回值是一个指针,但下面 的几道题还是感觉很迷惑。各位能否讲的详细点呢? (1)float(**def)[10] def是什么? (2)double*(*gh)[10] gh是什么? (3)double...
彩色荧光鼠标指针鼠标指针