摘要：题目要求输入一个整数数组，从中找到所有的三个整数组成一个数组，这三个整数的和为。要求不包括重复的结果思路一无这里使用了三个指针。先对数组进行排序。
题目要求
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: 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]
]
输入一个整数数组，从中找到所有的三个整数组成一个数组，这三个整数的和为0。要求不包括重复的结果
思路一：无hashset or hashmap
这里使用了三个指针。
先对数组进行排序。确定左侧固定的指针，然后移动右侧两个直至找到三个值和为0.如果当前三个指针的值小于0，则将中间的指针右移至下一个不同的值，如果小于0，则将最右侧指针左移至下一个不重复的值。一旦右侧和中间的指针重合，移动左侧指针至下一个不重复的值，并且初始化中间和右侧的指针
public List> threeSum2(int[] nums) {
List> result = new ArrayList>();
int length = nums.length;
if(length<3){
return result;
}
Arrays.sort(nums);
int i = 0;
while(i0) break;
int j = i+1;
int k = nums.length - 1;
while(j=0){
//消去右侧重复的数字
while(nums[k--] == nums[k] && j < k);
}
//消去和当前左指针相同的数字
while(nums[i] == nums[++i] && i < nums.length - 2);
}
}
return result;
}
思路二：有hashmap/hashset
利用hashmap/hashset是为了避开重复的值，但是效率值明显不如上一种方法高
public List> threeSum(int[] num) {
Arrays.sort(num);
List> list = new ArrayList>();
HashSet> set = new HashSet>();
for(int i=0;i l= new ArrayList();
l.add(num[i]);
l.add(num[j]);
l.add(num[k]);
if(set.add(l))
list.add(l);
j++;
k--;
}
else if(num[i]+num[j]+num[k]<0)
j++;
else
k--;
}
}
return list;
}
想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/66966.html
