李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
LeetCode-15三数之和
Leefs
2020-03-01 PM
1356℃
0条
# LeetCode-15三数之和 **题目描述** ```visual basic 给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。 注意:答案中不可以包含重复的三元组。 ``` 示例 > 给定数组 nums = [-1, 0, 1, 2, -1, -4], > > 满足要求的三元组集合为: > [ > [-1, 0, 1], > [-1, -1, 2] > ] **题解** 这道题的难点是不能包含重复的答案,对于[0,0,0,0,0]这个数组,答案只有一个[0,0,0]。 首先我们对数组先排序一次,在排好序的数组上,就很容判断前后元素是否相当,这样可以过滤掉重复的答案。 再定义三个指针,k,i,j如下图所示 ![38.LeetCode-15三数之和01.jpg][1] 指针`i`从左往右移动,且始终比`k`大一位,这样就保证不会跟`k`重叠, 指针`j`从右往左移动,且始终比`i`大,这样`i`和`j`就不会重叠,即三个指针都不会重叠。 在这个基础上,实现我们的主要逻辑: + 1.nums[k]>0时,可以直接跳出循环,因为nums[k]都比0大了,后面的nums[i]和nums[j]肯定更大,三者加起来肯定大于0 + 2.nums[k]和nums[k-1]相等,即前后元素重复了,需要过滤掉 + 3.如果nums[i]+nums[j]+nums[k]>0,即三者之和太大了,我们将j指针左移,因为三个数中最大的肯定是nums[j],将j左移就可以减小三者之和。 + 4.如果nums[i]+nums[j]+nums[k]<0,说明三者之和太小了,同理将i指针右移 + 5.如果nums[i]+nums[j]+nums[k]==0,这就是要找的答案,将其保存起来,同时i右移,j左移 i和j在移动的过程中还需要判断前后元素是否重复 ![38.LeetCode-15三数之和02.gif][2] **代码实现** ```java public static List
> threeSum2(int[] nums){ if(nums==null) { return new ArrayList
>(); } ArrayList
> res = new ArrayList
>(); int n = nums.length; //正式处理之前,先将数组排序 Arrays.sort(nums); //假设数组为[0,1,2,3,4,5,6,7,8,9,10] //第三个指针k最多到下标8位置,因为后面两个位置需要留给另外两个指针 for(int k=0;k
0,说明后面的元素肯定也大于0,最后结果肯定>0,故直接跳出 if(nums[k]>0) { break; } //如果当前元素和前面一个元素一样,忽略重复元素 if(k>0 && nums[k-1]==nums[k]) { continue; } //定义另外两个指针 i 和 j int i = k + 1; int j = n - 1; while(i
0,说明最右边的值太大了 if(tmp>0) { --j; while(i
> threeSum(int[] nums){ Arrays.sort(nums); //List
> list = new ArrayList<>(); Set
> result = new LinkedHashSet<>(); for(int i=0;i
(result); } ``` [1]: https://lilinchao.com/usr/uploads/2020/03/2453946507.jpg [2]: https://lilinchao.com/usr/uploads/2020/03/1473873459.gif
标签:
LeetCode刷题
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://lilinchao.com/archives/663.html
上一篇
Java实现RSA加密与解密
下一篇
线程通信之传统版生产者消费者模式
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
47
标签云
Ubuntu
机器学习
MyBatis
二叉树
Netty
工具
线程池
散列
Http
Git
Beego
高并发
Eclipse
RSA加解密
SpringCloudAlibaba
SpringCloud
Hadoop
JavaScript
Python
Java阻塞队列
Filter
HDFS
GET和POST
数据结构
锁
Spark SQL
JavaWEB项目搭建
Java编程思想
Elasticsearch
DataWarehouse
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞