Q15 三数之和
思路
我的思路,先排序,循环确定前两个值,最后一个值二分
看了题解:
最后两个值可以使用双指针,因为是有序的,而且是求和
注意重复值:
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> resultList = new ArrayList<>();
for (int i = 0; i < nums.length-2; i++) {
if (i!=0 && nums[i] == nums[i-1]){
continue;
}
resultList.addAll(twoSum(i+1, nums[i],nums));
}
return resultList;
}
private List<List<Integer>> twoSum(int index, int first, int[] nums) {
List<List<Integer>> resultList = new ArrayList<>();
int left = index;
int right = nums.length-1;
while (left<right){
if (nums[left] + nums[right] + first == 0){
List<Integer> list = new ArrayList<>(3);
list.add(first);
list.add(nums[left]);
list.add(nums[right]);
resultList.add(list);
left = findNext(left,nums);
} else if (nums[left] + nums[right] + first >0) {
right--;
}else {
left++;
}
}
return resultList;
}
//避免出现重复,如果右移和右边一样
private int findNext(int left, int[] nums) {
int index = left+1;
while (index < nums.length &&nums[index] == nums[left]){
index++;
}
return index;
}
```
原文地址:https://blog.csdn.net/weixin_44554979/article/details/140695529
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!