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）！