Q15 三数之和

思绪

我的思绪，先排序，循环确定前两个值，末了一个值二分
看了题解：
末了两个值可以使用双指针，因为是有序的，而且是求和
注意重复值：

1. public List<List<Integer>> threeSum(int[] nums) {
2.         Arrays.sort(nums);
3.         List<List<Integer>> resultList = new ArrayList<>();
4.         for (int i = 0; i < nums.length-2; i++) {
5.             if (i!=0 && nums[i] == nums[i-1]){
6.                 continue;
7.             }
8.             resultList.addAll(twoSum(i+1, nums[i],nums));
9.         }
10.         return resultList;
11.     }
13.     private List<List<Integer>> twoSum(int index, int first, int[] nums) {
14.         List<List<Integer>> resultList = new ArrayList<>();
15.         int left = index;
16.         int right = nums.length-1;
17.         while (left<right){
18.             if (nums[left] + nums[right] + first == 0){
19.                 List<Integer> list = new ArrayList<>(3);
20.                 list.add(first);
21.                 list.add(nums[left]);
22.                 list.add(nums[right]);
23.                 resultList.add(list);
25.                 left = findNext(left,nums);
26.             } else if (nums[left] + nums[right] +  first >0) {
27.                 right--;
28.             }else {
29.                 left++;
30.             }
31.         }
32.         return resultList;
33.     }
35.     //避免出现重复，如果右移和右边一样
36.     private int findNext(int left, int[] nums) {
37.         int index = left+1;
38.         while (index < nums.length &&nums[index] == nums[left]){
39.             index++;
40.         }
41.         return index;
42.     }
43.     ```
44.    

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。