Share some knowledge, post study notes or talk nonsense.

0%

[LeetCode 18] 4Sum (四数之和)

Description

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Notice that the solution set must not contain duplicate quadruplets.

Wrong Way

由于题目的Tag是HashTable,自然要用Hash的方法。

我一开始想把 4Sum 拆成两个 2Sum :

  1. 遍历 nums , 找出所有不同的2个数字的pair,把它们加到 unordered_map 里面,其中 key 即为两个数字的和,valuevector<vector<int>>对象。复杂度为O(n^2)
  2. 这样,我们只需每次先确定一个 sum ,找到这个 sum 下的vector<vector<int>>对象v1,然后再找到 target-sum 所对应的vector<vector<int>>对象v2,再两两组合即可。复杂度不会超过O(n^2)

错误之处:“从一个数组中选出4个数”不能简单地认为是两次“从一个数组中选出2个数”再组合。假如给的 nums 没有相同的数字,那么我们只需在第二步两两组合的过程中检查是否有相同的数字即可,有就不要组合,没有就组合,这个算法还是可以实现的。假如有相同的数字,我们不能作预处理“去重”(否则会少一些结果),因此也不能简单地在两两组合的过程中检查是否有相同的数字来解决这个问题。

Solutions

**Solution 0:**老老实实按照时间复杂度稍微高一点的算法

  1. 还是用一个 unordered_map,不过只是以每个数字为key,出现的次数为value

  2. 三层for循环,确定前三个数nums[i], nums[j], nums[k], 再检查target-nums[i]-nums[j]-nums[k]是否在unordered_map里面并且要求target>=nums[k]即可。但是当 nums 有相同的元素出现时, 最后的结果就会出现duplicate quadruplets,因此要进行以下三个操作:

    • 首先给 nums 排序。

    • 在给result添加quadruplets的时候:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      if(tmp_it != hashtable.end() && tmp >= nums[k]){
      int count = 1;
      if(nums[k] == nums[j]) count++;
      if(nums[k] == nums[i]) count++;
      if(tmp == nums[k] && tmp_it->second - count == 0)
      continue;
      else
      result.push_back(vector<int>{nums[i], nums[j], nums[k], tmp});
      }
    • 在那三层for循环结尾,要进行去重(以第二层for循环为例)。注意j+1<n-2防止最后一次判断的时候数组越界;以及用while而不是if来消除多个重复的数字:

      1
      2
      while(j+1 < n-2 && nums[j+1] == nums[j])
      ++j;

Solution 2:Hash Set,也是O(n^3)的时间复杂度。用了递归的思想,而且generalize到了kSum,不过它的Runtime(203ms)和Memory Usage(30MB)的排名也没好到哪里去:

  1. 首先对数组排序,先确定一个数字,然后对这个数字后面的部分调用(k-1)Sum。要注意duplicate的出现
  2. 直到进入到2Sum。2Sum的部分就是采用了hash的思想(利用unorderd_set)。也要注意duplicate的出现
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
// https://leetcode.com/problems/4sum/solution/

vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(begin(nums), end(nums));
return kSum(nums, target, 0, 4);
}

vector<vector<int>> kSum(vector<int>& nums, int target, int start, int k) {
vector<vector<int>> res;
if (start == nums.size() || nums[start] * k > target || target > nums.back() * k)
return res;
if (k == 2)
return twoSum(nums, target, start);
for (int i = start; i < nums.size(); ++i)
if (i == start || nums[i - 1] != nums[i])
for (auto &set : kSum(nums, target - nums[i], i + 1, k - 1)) {
res.push_back({nums[i]});
res.back().insert(end(res.back()), begin(set), end(set));
}
return res;
}
vector<vector<int>> twoSum(vector<int>& nums, int target, int start) {
vector<vector<int>> res;
unordered_set<int> s;
for (auto i = start; i < nums.size(); ++i) {
if (res.empty() || res.back()[1] != nums[i])
if (s.count(target - nums[i]))
res.push_back({ target - nums[i], nums[i]});
s.insert(nums[i]); // 边遍历边把元素加入hashtable里面,与在一开始就一下子把所有元素加进去相比,在防止出现duplicate时处理更方便
}
return res;
}

C++ Grammar:

autovector.back(), vector.insert(), unorderd_set

for循环的新用法(C++14): for(auto each1: vec1) {}//只访问不修改 for(auto & each1: vec1) {}//可访问可修改

Use vec.push_back({1, 2}) instead of vec.push_back(vector<int>{1, 2})

Solution 1:Two Pointers,只是twoSum 函数的实现不同,也是O(n^3)的时间复杂度,直接贴代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// https://leetcode.com/problems/4sum/solution/
vector<vector<int>> twoSum(vector<int>& nums, int target, int start) {
vector<vector<int>> res;
int lo = start, hi = nums.size() - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
if (sum < target || (lo > start && nums[lo] == nums[lo - 1]))
++lo;
else if (sum > target || (hi < nums.size() - 1 && nums[hi] == nums[hi + 1]))
--hi;
else
res.push_back({ nums[lo++], nums[hi--]});
}
return res;
}

Summary

  1. 善用递归简化代码
  2. 将大问题分解成小问题的思想,比如从kSum到(k-1)Sum…
  3. 考虑特殊及边界情况,比如数组中有数字相等的情况以及start == nums.size() || nums[start] * k > target || target > nums.back() * k 的情况
  4. 本题应用的算法:hash or two pointers