LeetCode:三数之和【15】
2024-09-25 09:36:15
LeetCode:三数之和【15】
题目描述
给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]
题目分析
我试了很多方法尝试去解决这个问题,但是都无果。后来在一次算法课上讲到了这个问题,3Sum问题,当时讨论出的解决方法如下:
List<List<Integer>> mylist = new ArrayList<>();
Arrays.sort(nums);
for(int i=0;i<nums.length;i++) {
for (int j = i+1;j<nums.length;j++) {
int k=Arrays.binarySearch(nums,-(nums[i]+nums[j]));
if(k>j)
{
ArrayList<Integer> al = new ArrayList<>();
al.add(nums[i]);al.add(nums[j]);al.add(nums[k]);
if(!mylist.contains(al))
mylist.add(al);
}
}
}
return mylist;
}
当时我对这个结局方案非常满意,可是现在不这么认为了。如果给出的数组是[0,0,0,0],那么就无法解决。
因为第三个值为0,无论如何到找到的都是中间那个,K不可能大于J。何况J还在自增。但是无论如何这是我们思考后的东西,都是有价值的。
Java题解
public List<List<Integer>> threeSum(int[] nums) {
/*
思路:从数组序列0开始依次取数作为第一个数字,剩下的两个数字指针从 数组的序列两端开始 相向取数字
并且每次都计算3个数的和,如为0则添加到列表,不为0,则根据和的大小,分别移动左右指针。 */
List<List<Integer>> result = new ArrayList<>();
if(nums.length < 3) return result;
Arrays.sort(nums);
int i = 0;
while(i < nums.length - 2) {
if(nums[i] > 0) break; int j = i + 1; //左指针
int k = nums.length - 1; //右指针 while(j < k) {
int sum = nums[i] + nums[j] + nums[k];
if(sum == 0) result.add(Arrays.asList(nums[i], nums[j], nums[k]));
if(sum <= 0) while(nums[j] == nums[++j] && j < k); //实现越过重复数字的功能
if(sum >= 0) while(nums[k--] == nums[k] && j < k); //同样实现越过重复数字的功能
} while(nums[i] == nums[++i] && i < nums.length - 2);//同上
}
return result;
}
反思
1.对 while循环的进一步理解:
while(nums[i]=nums[++j]&&j<k)
根据这条命令即可实现越过重复数字的功能.
2.双指针技术的应用。
最新文章
- ResourceHacker(4.5.30)单文件绿色汉化版
- Laravel Homestead安装笔记
- 引用模板中的类型时,切记要加上typename声明!!
- [deviceone开发]-cnodejs论坛移动端App
- vps mysql自动关闭
- HIVE: UDF应用实例
- cl_gui_cfw=>;flush
- HDU 4063 Aircraft(计算几何)(The 36th ACM/ICPC Asia Regional Fuzhou Site —— Online Contest)
- webstorm修改文件,webpack-dev-server不自动编译刷新的解决办法
- node.js的作用、回调、同步异步代码、事件循环
- Android开发效率—Eclipse快捷键
- iOS GCD 与 NSOperationQueue
- python 常用模块及方法
- poj2947
- Linux通过编辑器vi使用介绍
- Hadoop完全分布式搭建过程中遇到的问题小结
- 解决:无法将“Add-Migration”项识别为 cmdlet、函数、脚本文件或可运行程序的名称。请检查名称的拼写,如果包括路径,请确保路径正确,然后再试一次
- 打包优化实践(如何Code Spliting)
- python基础之作业1---用户登录
- Number 强制类型转换 int 强制转换整型 float 强制转换浮点型 complex 强制转换成复数 bool 强制转换成布尔类型,结果只有两种,要么True 要么 False ";";";bool 可以转换所有的数据类型 everything";";";