454. 四数相加II
题目链接：click here
文章讲解：click here
题目描述：给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。
思路：
只统计个数，那么就先把A+B的结果遍历存储在map里，键值对分别为{a+b的和，该和出现的个数}。
然后再遍历 C+D，看结果的相反数是否存在于map里，若存在，则将结果增加对应键值对的‘值’。代码：
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
39class Solution
{
public:
int fourSumCount(vector<int> &nums1, vector<int> &nums2, vector<int> &nums3, vector<int> &nums4)
{
unordered_map<int, int> um;
for (auto &num1 : nums1)
{
for (auto &num2 : nums2)
{
int res = num1 + num2;
if (um.find(res) != um.end())
{
um[res]++;
}
else
{
um[res] = 1;
}
}
}
int result = 0;
for (auto &num3 : nums3)
{
for (auto &num4 : nums4)
{
int res = num3 + num4;
if (um.find(-res) != um.end())
{
result += um[-res];
}
}
}
return result;
}
};讲解代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
unordered_map<int, int> umap; //key:a+b的数值，value:a+b数值出现的次数
// 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中
for (int a : A) {
for (int b : B) {
umap[a + b]++;
}
}
int count = 0; // 统计a+b+c+d = 0 出现的次数
// 再遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
for (int c : C) {
for (int d : D) {
if (umap.find(0 - (c + d)) != umap.end()) {
count += umap[0 - (c + d)];
}
}
}
return count;
}
};时空复杂度分析：
双重for ：O() 时间复杂度
使用unordered_map存储,至多 种a+b的和：O() 空间复杂度
383. 赎金信
题目链接：click here
文章讲解：click here
题目描述：给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
思路：
和昨天的异位词相似，只不过这里杂志集可以包含更多的元素，但一定要含有足够的能表达赎金信的元素。
遍历杂志构建map，键值对分别是{char,个数}
再遍历赎金信的char，map里查找，若无，则为false，若有，则对应键值对的值减少1，并检查值是否为负数了，也就是杂志上的该char的数量不够。讲解思路：
可以利用char只有从a->z的26个数字的先验信息，如昨天的异位词一样使用数组。代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution
{
public:
bool canConstruct(string ransomNote, string magazine)
{
unordered_map<char, int> um;
for (auto c : magazine)
{
um[c]++;
}
for (auto c : ransomNote)
{
um[c]--;
if (um[c] < 0)
{
return false;
}
}
return true;
}
};时空复杂度分析：
遍历string 1和2：O(n+m) 时间复杂度
使用unordered_map存储数组2结果：O(m) 空间复杂度
15. 三数之和
题目链接：click here
文章讲解：click here
题目描述：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
思路：
我一开始按照昨天的二数之和的方法，将三数之和写为：遍历第一个数，然后使用二数之和的方法查找符合要求的第二、三个数。
然后再用 set 的方法来去除重复的结果。
但是这种做法通不过力扣的第310个测试案例[几百个0的数组]，超时。所以肯定需要一些预剪枝的操作来加快无谓的查找。
如何跳过？才能不漏？讲解提供了关键操作，先排序，再遍历时，碰到相同元素即可跳过。
讲解中还提供了排序后的二数之和的新方法：双指针法
原理和二分法是一样的，即，左右指针分别向中间移动，若当前二数之和大于target，则说明右值较大，需要左移右指针；若小于target，则右移左指针，相等，则意味着找到了符合条件的两数，协同最开始的第一个数，构成了符合条件的三数。
其次，这里也就可以和二分法一样进行剪枝，若左右指针移动前后，值不变，则可继续移动。
总的来说，要求结果里不能重复时，先排序可能会降低后续算法的复杂度。
代码：
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
67class Solution
{
public:
vector<vector<int>> threeSum(vector<int> &nums)
{
std::sort(nums.begin(), nums.end());
vector<vector<int>> res;
int n = nums.size();
int left = 0;
int right = n - 1;
for (int i = 0; i < n - 2; i++)
{
if (nums[i] > 0)
{
break;
}
if (i > 0 && nums[i] == nums[i - 1]) // 移动过了，和自己之前的值比，是否没发生变化
{
continue;
}
int target = -nums[i];
left = i + 1;
right = n - 1;
int last_left = 1e6, last_right = 1e6;
while (left < right)
{
if (last_left == nums[left])
{
left++;
continue;
}
if (last_right == nums[right])
{
right--;
continue;
}
if (nums[left] + nums[right] > target)
{
last_right = nums[right];
right--;
}
else if (nums[left] + nums[right] < target)
{
last_left = nums[left];
left++;
}
else
{
last_right = nums[right];
last_left = nums[left];
res.push_back({nums[i], nums[left], nums[right]});
right--;
left++;
}
}
}
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
48class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
// 找出a + b + c = 0
// a = nums[i], b = nums[left], c = nums[right]
for (int i = 0; i < nums.size(); i++) {
// 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
if (nums[i] > 0) {
return result;
}
// 错误去重a方法，将会漏掉-1,-1,2 这种情况
/*
if (nums[i] == nums[i + 1]) {
continue;
}
*/
// 正确去重a方法
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
// 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
/*
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
*/
if (nums[i] + nums[left] + nums[right] > 0) right--;
else if (nums[i] + nums[left] + nums[right] < 0) left++;
else {
result.push_back(vector<int>{nums[i], nums[left], nums[right]});
// 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// 找到答案时，双指针同时收缩
right--;
left++;
}
}
}
return result;
}
};时间复杂度：O()，第一个数遍历了数组 + 二数之和遍历了剩余的元素
空间复杂度：O(1)，一些临时存储
18. 四数之和
题目链接：click here
文章讲解：click here
题目描述：题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
思路：
遍历第一个数，剩余的三数，直接套用上题的接口找对应的target，微微修改一些逻辑即可。
比如，剪枝的时候，要跳过，不光光是当前值 > target，还要求当前值 > 0。
三数之和之所以可以直接 target > 0 就剪枝，是因为恰巧 target = 0.代码：
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104class Solution
{
public:
vector<vector<int>> fourSum(vector<int> &nums, int target)
{
std::sort(nums.begin(), nums.end());
vector<vector<int>> res;
int n = nums.size();
int last_size1 = 0;
for (int i = 0; i < n - 3; i++)
{
// 剪枝处理
if (nums[i] > target && nums[i] >= 0) {
break; // 这里使用break，统一通过最后的return返回
}
if (i > 0 && nums[i] == nums[i - 1])
{
continue;
}
long target_of_three = target - nums[i];
threeSum(nums, i + 1, target_of_three, res);
for (int j = last_size1; j < res.size(); j++)
{
res[j].push_back(nums[i]);
}
last_size1 = res.size();
}
return res;
}
void threeSum(vector<int> &nums, int start_idx, long target, vector<vector<int>> &res)
{
int n = nums.size();
int last_size = res.size();
for (int i = start_idx; i < n - 2; i++)
{
// 剪枝处理
if (nums[i] > target && nums[i] >= 0) {
break; // 这里使用break，统一通过最后的return返回
}
if (i > start_idx && nums[i] == nums[i - 1])
{
continue;
}
long target_of_two = target - nums[i];
twoSum(nums, i + 1, target_of_two, res);
for (int j = last_size; j < res.size(); j++)
{
res[j].push_back(nums[i]);
}
last_size = res.size();
}
}
void twoSum(vector<int> &nums, int start_idx, long target, vector<vector<int>> &res)
{
int n = nums.size();
int left = start_idx;
int right = n - 1;
int last_left = 0, last_right = 0;
while (left < right)
{
if (left > start_idx && last_left == nums[left])
{
left++;
continue;
}
if (right < n - 1 && last_right == nums[right])
{
right--;
continue;
}
if ((long)nums[left] + nums[right] > target)
{
last_right = nums[right];
right--;
}
else if ((long)nums[left] + nums[right] < target)
{
last_left = nums[left];
left++;
}
else
{
last_right = nums[right];
last_left = nums[left];
res.push_back({nums[left], nums[right]});
right--;
left++;
}
}
}
};时间复杂度：O() 相当于三重for循环
空间复杂度：O(1) 一些临时变量
今日收获
个人博客更新。若Blog有误或是有其他想交流的，左侧有联系方式。
复习：
今日核心思想：若要求结果中元素不能重复，可以考虑先排序，再搜索，既可以确保不重复，又能提供更强的剪枝依据，加快计算。四数相加II：只统计满足情况的数量，直接遍历AB->构建map->遍历CD->查找map，即可。
赎金信：规模有限的比对问题，可以先用有限大小的数组保存其中一个词条的字频，再遍历另一个词条核对字频
字频符合要求则比对成功。昨天异位词的要求是“词频完全一致”，这里的要求是“杂志词频>=赎金信词频”。
三数之和：核心是去重和剪枝，以及排序后的二数之和的双指针写法，原理和二分法是一样的。
四数之和：在三数之和的基础上写就比较简单了。耗时：3h