模板解题 NSum

LeetCode

LeetCode 第一题就是很经典的题目： twoSum ，twoSum 的解法有很多种，最经典的方法就是 排序+双指针 ，如果我们掌握了这个核心解法，那么去解 NSum 的问题将会很easy！

划重点 排序+双指针 是我们解决 NSum 的核心思想。

一. twoSum 问题

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这倒提的解法可以看我的 Github Day1120TowNum

由于这道题是让求数组的下标，跟我们要求数组里面的值相加等于target有点出入，所以这里不展开描述了。项目里面提供了两个解法，一个是利用HashMap去解，另一个是利用 排序+双指针 思路去解。

下面我们将题目描述变一下：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的 值。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [2, 7]

解决这个问题的核心是使用排序+双指针：

  • 首先对数组进行排序
  • 利用双指针，从两端相向相加跟target的值进行比较

问题的关键在于不能重复，假如数组为 [2, 7, 11, 15] ,target = 9 ,那么输出 [2,7],[7,2] 就是重复的项，所以我们需要注意将重复的值去掉。
如果数组为[2, 7, 2, 7, 11, 15] ,target = 9 ,那么输出的 [2,7],[2,7] 也属于重复的项，同样需要将重复的项去掉。

代码如下：

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
public static List<List<Integer>> twoSum(int[] nums, int start, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        //1.排序
        Arrays.sort(nums);
        //2.定义两个指针  low heigh
        int low = start, heigh = nums.length - 1;

        while (low < heigh) {
            int sum = nums[low] + nums[heigh];
            //3.定义两个临时变量用来存储  当前两个指针的值  left 跟 right
            int left = nums[low], right = nums[heigh];
            if (sum < target) {
                //受4的启发 跳过所有重复的元素
                while (low < heigh && nums[low] == left) {
                    low++;
                }
            } else if (sum > target) {
                //受4的启发 跳过所有重复的元素
                while (low < heigh && nums[heigh] == right) {
                    heigh--;
                }
            } else {
                List<Integer> list = new ArrayList<Integer>();
                list.add(left);
                list.add(right);
                result.add(list);
                //4.跳过所有重复的元素
                while (low < heigh && nums[low] == left) {
                    low++;
                }
                while (low < heigh && nums[heigh] == right) {
                    heigh--;
                }
            }
        }
        return result;
    }

这样我们就写出来一个通用的 twoSum 模板了，针对题目变种后，问题将会迎刃而解。

  • 时间复杂度： 循环是O(N)，排序是O(NlogN),所以整体的时间复杂度是 O(NlogN)

二. 3Sum 问题

题目描述：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

问题上升到 3Sum ,其实我们只有将这个问题转化成 twoSum,问题就会迎刃而解，怎么转换呢？穷举。我们求三个数的和是 target，那么也就是说我们可以固定住第一个数，然后去求除第一个数以外的其他数任选两个数的和为 target-num[0] ，依次类推，就是求target-num[i] 的 twoSum。

所以代码如下：

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
public static List<List<Integer>> twoSum(int[] nums, int start, int target) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    Arrays.sort(nums);
    //左指针改成 start，其他不变
    int low = start, heigh = nums.length - 1;

    while (low < heigh) {
        ...
    }
    return result;
}

public static List<List<Integer>> threeSum(int[] nums, int start, int target) {
    Arrays.sort(nums);
    int n = nums.length;
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    for (int i = start; i < nums.length; i++) {
        List<List<Integer>> listData = twoSum(nums, i + 1, target - nums[i]);
        for (List<Integer> data : listData) {
            data.add(nums[i]);
            result.add(data);
        }
        //跳出第一个数字重复的情况
        while (i < n - 1 && nums[i] == nums[i + 1]) {
            i++;
        }
    }

    return result;

}
  • 时间复杂度 排序O(NlogN),twoSum O(N), threeSum 里面循环调用twoSum，所以时间复杂度是 O(NlogN+N*N)=O(N^2)

4Sum 问题

题目描述：

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决 4Sum 的思路跟解决 3Sum 的思路一样，我们通过穷举将问题转换成 3Sum ，问题就得到了解决。

代码如下：

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
public static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for (int i = 0; i < nums.length; i++) {
            List<List<Integer>> listData = threeSum(nums, i + 1, target - nums[i]);
            for (List<Integer> data : listData) {
                data.add(nums[i]);
                result.add(data);
            }
            while (i < n - 1 && nums[i] == nums[i + 1]) {
                i++;
            }
        }

        return result;
    }

    public static List<List<Integer>> threeSum(int[] nums, int start, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        // i的起始值改为start，其他保持不变
        for (int i = start; i < nums.length; i++) {
            ...
        }

        return result;

    }
  • 时间复杂度： 4Sum 循环了 3Sum ，所以时间复杂度是 O(N^3)

NSum 问题

5Sum 根据 4Sum 可以得出，4Sum 根据 3Sum 可以得出，3Sum 根据 2Sum 可以得出，所以那就 递归 吧。。。

  • 递归条件

    nums ,n,start,target

  • 递归终止条件

    n如果小于2则退出递归

所以代码大概的递归框架如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public static List<List<Integer>> nSum(int[] nums, int n, int start, int target) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    //递归结束条件
    if(n<2){
        return result;
    }
    
    if(n==2){
        // twoSum
    }else {
        //递归逻辑
    }
}

我们现在根据递归框架，往代码里面进行填肉：

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
public static List<List<Integer>> nSum(int[] nums, int n, int start, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        //递归结束条件
        int sz=nums.length;
        if (n < 2) {
            return result;
        }
        if (n == 2) {
            // twoSum
            result = twoSum(nums, start, target);
        } else {
            //当n>2 时,递归计算 (n-1)Sum的结果
            for (int i = start; i < nums.length; i++) {
                List<List<Integer>> lists = nSum(nums, n - 1, i + 1, target - nums[i]);
                for (List<Integer> data : lists) {
                    data.add(nums[i]);
                    result.add(data);
                }

                while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                    i++;
                }
            }

        }
        return result;
    }

总结

总结一下：NSum 的核心思想就是 排序+双指针 ，当然我们为了求 NSum ，最后用到了递归。虽然方法不是最快的，但是这个思路是最方便解这样的题的。

参考资料

赏

×

纯属好玩

扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦

本文标题:模板解题 NSum

文章作者:独ǒ无②

发布时间:2020年12月03日 - 10时58分

最后更新:2020年12月03日 - 13时36分

原始链接:http://pvphero.github.io/2020/12/03/20200518Sum/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 一. twoSum 问题
  2. 2. 二. 3Sum 问题
  3. 3. 4Sum 问题
  4. 4. NSum 问题
  5. 5. 总结
    1. 5.1. 参考资料
,