3 Sum leetcode java
2024-10-21 23:22:05
题目：
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:
- Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
- 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)
题解：
3 Sum是two Sum的变种，可以利用two sum的二分查找法来解决问题。
本题比two sum增加的问题有：解决duplicate问题，3个数相加返回数值而非index。
首先，对数组进行排序。
然后，从0位置开始到倒数第三个位置（num.length-3)，进行遍历，假定num[i]就是3sum中得第一个加数，然后从i+1的位置开始，进行2sum的运算。
当找到一个3sum==0的情况时，判断是否在结果hashset中出现过，没有则添加。(利用hashset的value唯一性）
因为结果不唯一，此时不能停止，继续搜索，low和high指针同时挪动。
时间复杂度是O(n2)
实现代码为：
1 public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
2 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
3 if(num.length<3||num == null)
4 return res;
5
6 HashSet<ArrayList<Integer>> hs = new HashSet<ArrayList<Integer>>();
7
8 Arrays.sort(num);
9
for(int i = 0; i <= num.length-3; i++){
int low = i+1;
int high = num.length-1;
while(low<high){//since they cannot be the same one, low should not equal to high
int sum = num[i]+num[low]+num[high];
if(sum == 0){
ArrayList<Integer> unit = new ArrayList<Integer>();
unit.add(num[i]);
unit.add(num[low]);
unit.add(num[high]);
if(!hs.contains(unit)){
hs.add(unit);
res.add(unit);
}
low++;
high--;
}else if(sum > 0)
high --;
else
low ++;
}
}
return res;
}
同时，解决duplicate问题，也可以通过挪动指针来解决判断，当找到一个合格结果时，将3个加数指针挪动到与当前值不同的地方，才再进行继续判断，代码如下：
1 public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
2 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
3 if(num.length<3||num == null)
4 return res;
5
6 Arrays.sort(num);
7
8 for(int i = 0; i <= num.length-3; i++){
9 if(i==0||num[i]!=num[i-1]){//remove dupicate
int low = i+1;
int high = num.length-1;
while(low<high){
int sum = num[i]+num[low]+num[high];
if(sum == 0){
ArrayList<Integer> unit = new ArrayList<Integer>();
unit.add(num[i]);
unit.add(num[low]);
unit.add(num[high]);
res.add(unit);
low++;
high--;
while(low<high&&num[low]==num[low-1])//remove dupicate
low++;
while(low<high&&num[high]==num[high+1])//remove dupicate
high--;
}else if(sum > 0)
high --;
else
low ++;
}
}
}
return res;
}
最新文章
- HDU3571 N-dimensional Sphere(高斯消元 同模方程)
- ASP.NET 递归将分类绑定到 TreeView
- hadoop的ganglia数据监控
- 自定义强大的C#网络操作基础类（NetHelper）
- ORACLE 优化
- 内核增加支持yaffs2错误问题汇总
- android NDK jni下的c文件 Unresolved inclusion
- 再造 “手机QQ” 侧滑菜单（三）——视图联动
- 浅谈Storm流式处理框架（转）
- 谈Web应用系统的可维护性
- C++ static成员变量与static成员函数
- pureftpd.passwd解析
- C# 调整控件的Z顺序
- C# p2p UDP穿越NAT,UDP打洞源码
- c的链接详解
- poj----2155 Matrix(二维树状数组第二类)
- C++/CLI中class成员声明与实现分开在不同文件时必须添加namespace
- 对称矩阵与压缩存储算法（java实现）
- Linux入门第四天——shell基础
- High School: Become Human（数学思维）