18. 四数之和

原题链接：

18. 四数之和
https://leetcode.cn/problems/4sum/description/

完成情况：

解题思路：

/**
* //HashMap只能记录key，value的结果
* //而不能记录产生这个结果的过程
*
* @param nums
* @param target
* @return
*/

思路全在代码注释里
1

参考代码：

package LeetCode算法题;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class __18四数之和 {
    /**
     *         //HashMap只能记录key，value的结果
     *         //而不能记录产生这个结果的过程
     *
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        //参考之前的三数求和，以及四数直接结果求和，
        //难道是构造两两的两对，然后一个两对的集合，去和另外两个数去判断？？？
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int len = nums.length;
        if (nums == null || len < 4){
            return res;
        }
        Arrays.sort(nums);  //初始先将所有元素排好序，这样可以避免混乱的找要求数字
        for (int i=0;i<len-3;i++){
            if (i>0 && nums[i] == nums[i-1]){   //从第二个数开始判断
                continue;       //并且去重
            }
            //取完重复之后，固定一个点，剩下指针指向三个节点
            //然后进行左右判断
            if ((long)nums[i] + nums[i + 3] + nums[i + 2] + nums[i+1] > target){
                break;      //如果最左边四个数还比target大，那么说明已经没有数满足target了。
            }
            if ((long)nums[i] + nums[len - 3] + nums[len - 2] + nums[len-1] < target){
                //nums[i] + nums[len - 3] + nums[len - 2] + nums[len-1]
                continue;   //+最大的三个数，如果还小于的话，那么说明nums[i]还可以左走
            }
            /*
            int Left = i+1,Right = len -1;
            while (Left < Right){
            同三个数比大小，但这里是四个数，因此还剩三个数，
            所以需要指出三个指针
             */
            for (int j = i+1;j<len-2;j++){
                if (j>i+1 && nums[j] == nums[j-1]){     //继续去重
                    continue;
                }
                if ((long)nums[i] + nums[j] + nums[j+1] + nums[j+2] > target){
                    //如果头四个数大于target
                    break;
                }
                if ((long)nums[i] + nums[j] + nums[len-2]+nums[len - 1] < target){
                    //如果定了指针的左边两个数 + 右边的两个数   小于target
                    continue;   //说明左边的数，小了
                }
                    /*
                        int Left = i+1,Right = len -1;
                        while (Left < Right){
                        同三个数比大小，但这里是四个数，因此还剩三个数，
                        所以需要指出三个指针
                     */
                //然后仿照三个数比大小，锁定left，right去模仿移动
                //此时的指针，分别是i，j，left，right
                int left = j+1,right = len - 1;
                while (left < right){
                    long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target){
                        res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while (left<right && nums[left] == nums[left+1]){
                            left++;
                        }
                        left++;
                        while (left < right && nums[right] == nums[right-1]){
                            right--;
                        }
                        right--;
                    }else if (sum<target) { //左边小了
                        left++;
                    }else {     //右边大了
                        right--;
                    }
                }
            }
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

错误经验吸取