Leetcode 中子集和问题及其解法

文章目录

1. 问题本身（What）
2. 为什么要解决这类问题，这类问题要解决的实际问题又会是什么（Why、When）
3. 如何求解，及求解思路（How）

问题本身（What）

LeetCode 众多问题中有一类问题是 xSum 问题，例如：

这一类问题泛化后的问题是：
给定一个数组，返回X个数组元素之和为给定目标数的元素列表。

为什么要解决这类问题，这类问题要解决的实际问题又会是什么（Why、When）

该问题是计算复杂度理论和密码学中一个重要问题，特别的该问题是著名的N-NP问题中的NP完全问题。
wiki – Subset sum problem

如何求解，及求解思路（How）

3sum

这里我们选择3Sum作为讲解例子：

关于题目本身

首先对于3Sum问题，题目本身有什么需要注意的点么？仔细想来可能会有以下这些：

作为输入的参数 nums 数组是否有可能为空？
作为输入的参数 nums 数组长度是否大于3？

如果以下两个问题的答案都是有可能，那么这两种边界条件下应该返回什么样的结果？ null还是空列表？

所有可能解

其次，所有可能的解法会有以下这些：

Brutal Force （backtrace）
直接想到的，也是直觉算法就是穷举所有可能的组合（俗称傻算），然后找出符合条件的元素；
这里需要注意的是需要做元素去除重复元素的处理。

loop i: 0 -> length:
    loop j: i + 1 -> length:
        loop k: j + 1 -> length:
            if nums[i] + nums[j] + nums[k] == 0 :
                add_to_result_set

对于这里的时间和空间复杂度也相对一目了然:
时间复杂度: $O(N^3)$
空间复杂度：$O(1)$

基于BF的改进（使用动态数据结构优化一层循环）
显然，对于以上的$O(N^3)$复杂度的算法，算法效率并不高，那么如何提升效率呢？常见的提升代码执行效率的思想是用空间换时间，沿着这个思路继续想下去，我们发现可以使用 Map / Set 这样的动态数据结构来优化，用额外的空间来换取一层时间复杂度。伪代码如下所示：

loop element -> nums:
    Map.put(element)

loop i -> length:
    loop j -> length:
            if Map.exists(0 - (nums[i] + nums[j])) :
                add_to_result_set

在使用具体语言实现的时候需要注意的同样是如何去除重复的三元组组合，这里给出的一种解决思路是，首先将数组排序，然后在添加结果到结果集之前

排除掉自己和自己组合（数组下标相同）的情况和
数组中元素重复（数组下标不同但值相同）情况
具体实现可以参看我的Github实现： 3sum : threeSumWithMap

对于这里的时间和空间复杂度也相对一目了然:
时间复杂度: $O(N^2)$
空间复杂度：$O(N)$

基于第二种解法的进一步优化

这里看似在时间效率上已经是最优了，但是还是使用了额外的存储空间，那么是否存在时间复杂度: $O(N^2)$，空间复杂度：$O(1)$ 的算法呢？
实际上是有的，因为数组是排好序的，受二分查找算法的启发，可以通过left，right指针来寻找符合条件的两个元素，具体的伪代码如下：

loop i -> length:
    a = nums[i];
    left = i + 1;
    right = length - 1;
    while (left < right>) {
        if (a + nums[left] + nums[right] > 0) right--;
        else if (a + nums[left] + nums[right] < 0) left++;
        else {
            add_to_result_set
        }
    }

在使用具体语言实现的时候需要注意的同样是如何去除重复的三元组组合,具体实现可以参看我的Github实现： 3sum : threeSum

对于这里的时间和空间复杂度也相对一目了然:
时间复杂度: $O(N^2)$
空间复杂度：$O(1)$

这样看来，第三种解法目前是在时间和空间复杂度的最优解。

2sum

int[] twoSum(int[] nums, int target) {
  if (nums == null) return null;

  HashMap<Integer, Integer> map = new HashMap<>();
  int count = nums.length;
  for (int i = 0; i < count; i++) {
    if (map.get(target - nums[i]) != null && map.get(target - nums[i]) != i) {
      return new int[] {i, map.get(target - nums[i])};
    }

    map.put(nums[i], i);
  }

  return null;
}

4sum

Github 4sum in brutal force way - fourSumInBrutalForceWay

Github 4sum with map - fourSumWithMap
Github 4sum with 2 pointers - fourSum