15.3Sum
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.
实现思路
- 如何快速找出3个数的和为0
先排序，从头开始遍历，选定一个元素，然后再后从首尾取数，最终选定剩余的两个元素 - 找出的结果要保证是不重复的
查找过程中，对于相同的数进行排除
实现代码
public class Solution {
/*要考虑的问题：
如何快速找出3个数的和为0；先排序，从头开始遍历，选定一个元素，然后再后从首尾取数，最终选定剩余的两个元素
找出的结果要保证是不重复的；查找过程中，对于相同的数进行排除
*/
public List<List<Integer>> threeSum(int[] nums) {
//将数组进行排序
Arrays.sort(nums);
List<List<Integer>> rs = new LinkedList<>();
for(int i = 0; i < nums.length - 2; i ++){
int sum = 0 - nums[i];
//若前后的元素一致，那么可以跳过该操作
if(i == 0 ||(i > 0 && nums[i] != nums[i-1])){
int lo = i+1;
int hi = nums.length-1;
//首尾搜索
while(lo < hi){
//获得结果，则添加
if(nums[lo]+nums[hi] == sum){
rs.add(Arrays.asList(nums[i],nums[lo],nums[hi]));
//将相同的元素忽略掉
while(lo<hi && nums[lo] == nums[lo+1]) lo ++;
while(lo<hi && nums[hi] == nums[hi-1]) hi --;
lo ++; hi --;
} else if (nums[lo]+nums[hi] < sum)
lo ++;
else
hi --;
}
}
}
return rs;
}
}
