力扣15题、18题（三数之和，四数之和）

15、三数之和

基本思想：

利用排序后的使用双指针的两数之和

具体实现：

1、将数组排序

2、for循环，i从下标0的地方开始，left定义在i + 1位置上，right定义在数组结尾位置上

3、如果nums[i] + nums[left] + nums[right] > 0 

     说明三数之和大了，right向左移动

4、如果nums[i] + nums[left] + nums[right] < 0 

     说明三数之和小了，left向右移动

5、重复4,5直到left，right相遇，再执行下一个i

代码：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++){
            if (nums[i] > 0){
                return result;
            }
            if (i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0){
                    right--;
                } else if (sum < 0){
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
}

18、四数之和

基本思想：

双指针

具体实现：

在三数之和的基础上再套一层for循环

与三数之和不同的地方是target为任意值

三数之和的双指针解法是一层for循环nums[i]为任意值，

然后循环内有left和right下表作为双指针，找到nums[i] + nums[left] + nums[right] == 0

四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，

然后循环内有left和right下表作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况

代码：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++){
            if (i > 0 && nums[i - 1] == nums[i]){
                continue;
            }
            for (int j = i + 1; j < nums.length; j++){
                if (j > i + 1 && nums[j - 1] == nums[j]){
                    continue;
                }

                int left = j + 1;
                int right = nums.length - 1;
                while (right > left){
                    int sum = nums[i] + nums[j] + nums[left] +nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target){
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[right], nums[left]));
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right < left && nums[left] == nums[left + 1]) left++;

                        left++;
                        right--;
                    }
                }
            }

        }
        return result;
    }
}