摘要：要求序列不重复。这个问题比较复杂的一点是，还要处理重复的数据。为了简化我们的操作，我们先对数组进行预排序。排序之后，对于求两个数和的问题，可以通过和两个指针从两边查找，也简化了操作时间。解法防止重复序列
题目详情
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.给定一个整数数组s，我们要找出s中是否有三个不同元素的加和等于0，如果有，输出所有满足条件的序列。要求序列不重复。
For example, 输入数组S = [-1, 0, 1, 2, -1, -4],
返回的结果集应该是：
[
[-1, 0, 1],
[-1, -1, 2]
]
想法
通过减治的思想，我们可把三个数求和的问题，减治为对于数组中不重复的元素nums[i],求两个数的和等于-nums[i]的过程。
这个问题比较复杂的一点是，还要处理重复的数据。为了简化我们的操作，我们先对数组进行预排序。
经历了预排序，我们判断一个元素是否重复，只需要比较它和之前位置的元素是否相等就可以了。
排序之后，对于求两个数和的问题，可以通过low和high两个指针从两边查找，也简化了操作时间。
解法
public List> threeSum(int[] nums) {
int length = nums.length;
List> res = new ArrayList>();
Arrays.sort(nums);
for(int i=0;i0 && nums[i] != nums[i-1])){
int low = i+1;
int high = length-1;
int target = -nums[i];
while(low < high){
if(nums[low]+nums[high] == target){
res.add(Arrays.asList(nums[i], nums[low], nums[high]));
while(low < high && nums[low] == nums[low+1])low++;
while(low < high && nums[high] == nums[high-1])high--;
low++;
high--;
}else if(nums[low]+nums[high] < target){
low++;
}else{
high--;
}
}
}
}
return res;
}
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/70984.html
