链接
454.四数相加II
383. 赎金信
15. 三数之和
18. 四数之和
哈希表总结篇
知识
454.四数相加II
cpp中的map中的value是支持++操作的，且value可以通过key直接索引到，就像普通的数组那样。
383. 赎金信
不仅对vector可以用范围遍历，对string类型的变量和普通的数组也可以用范围遍历的写法来简化代码。似乎范围遍历的速度要稍快于普通的for循环遍历。
cpp中，可以用erase函数来删除string类型变量的第j个字符，有两种写法：
string.erase(j, 1);string.erase(s.begin() + j);cpp中，如果想使用变量类型来给变量命名，需要使用std，有如下例子：
1
2
3
4
5
6
7
8
int main() {
std::set<int> set; // 使用 "set" 作为变量名
set.insert(1);
set.insert(2);
return 0;
}在这个例子中，
set是作为std::set<int>类型的变量名使用的。由于std::set是在std命名空间中定义的，而变量set是在局部作用域中定义的，所以编译器能够区分这两者。
18. 四数之和
- 将四数之和由int类型转换为long类型：
(long) nums[i] + nums[j] + nums[l] + nums[r] > target
初次尝试
454.四数相加II
这道题肯定是要用map做哈希的，且map的key用来存储元素的值，map的value用来存储元素的索引。此题和两数之和为target有较多的相同点，但也有些不同。若四个数相加为0，则其中的数两两互为相反数。但这种想法是不对的，可以存在2, 4, -3, -3的情况。对这题的算法我暂时想不出来什么好主意。
383. 赎金信
看着就是242.有效的字母异位词的变式，若前面那个字符串可以由后面那个字符串中的字母构成，则返回true，否则返回false。本质就是看后面的字符串是否包含前面的字符串。因为两个字符串都只是由小写字母构成，因此用数组做哈希足矣。根据这个思路，我写出了如下代码：
1 | class Solution { |
采用范围遍历的方法，可以把上述代码写得更简洁：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
// ransomNote < magazine return true
// else return false
int N[26] = {0};
for (char r: ransomNote)
N[r - 'a'] ++ ;
for (char m: magazine)
N[m - 'a'] -- ;
for (int i: N)
if (i > 0)
return false;
return true;
}
};
15. 三数之和
这道题的题目我都不太理解，什么叫答案中不可以包含重复的三元组。直到我看到了示例1，明白了这个意思是可能存在情况：两个三元组，它们的索引组成的三元组可能不同，但这两个三元组本身的数值是完全相同的（忽略顺序），此时这两个三元组只能算作一个。这道题应该可以用哈希法，但需要去重。本题我认为有三个难点：
- 枚举完一个数，怎么去寻找另外两个数
- 用什么数据结构维护另外两个数
- 如何去重
18. 四数之和
本题应该依然是双指针算法。但需要注意去重的操作。我的思路是先对数组进行排序，然后让a = i, b = i + 1, c = i + 2, d = nums.size() - 1。然后一边向后移动a, b和c，一边对a,b和c去重，一边向前移动d，一边对d去重。根据以上思路，我写下了以下的代码：
1 | class Solution { |
以上代码测试样例通过了229 / 294，可见思路是对的，但细节仍不完美。我将在实现部分进一步优化细节。
实现
454.四数相加II
四数相加和四数之和题目看起来相似，但前者是哈希表中的经典题目，后者用哈希表的方法不太合适。其实只需要知道有多少对四数之和为0，不需要知道每一对的具体数值。
本题不需要去重，因此相对简单，四数之和则需要考虑去重。举例：四个数组，每个数组中都有n个0，则返回的结果是n。
思路：遍历数组A和B，将从这两个数组取出的元素a + b放入map中；再遍历数组C和D，求得c + d，再判断map中有无我们想要的元素-(c + d)，有则count += -(c+d)出现过的次数（即map中key为-(c+d)的元素的value）。
本题的数据范围很大，因此用数组来做哈希不可取，只能考虑set/map。因为不仅需要将a + b放入哈希结构中，还需要统计a + b出现过多少次，因此用map。用map的key存a + b的值，用map的value存a + b出现的次数。
时间复杂度：O(n^2) + O(n^2)，还是O(n^2)。如果先遍历一个数组，再遍历三个数组，则时间复杂度是O(n^3)。
我知道上述思路后，尝试写代码，出现一个问题：不知道如何统计数组A和数组B中各取一个元素求和后的值出现的次数。我把简单的问题想复杂了，map中的value是支持++操作的，且value可以通过key索引到，因此直接：map[num1 + num2] ++ ;即可，这个代码的意思是：若num1 + num2的值出现过，则其value += 1；若没出现过，则相当于：map.insert({num1 + num2, 1})。写出了以下的代码：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
26class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
// 遍历nums1和nums2数组，将两个数组各取一个值的和作为key，和出现的次数作为value存入map中
unordered_map<int, int> sum;
for (int num1: nums1)
for (int num2: nums2)
sum[num1 + num2] ++ ; // 和为num1 + num2的值的出现次数 + 1
// 遍历nums3和nums4数组，设两个数组各取一个值的和是c + d
// 若map中出现了-(c + d)，则count += value
int count = 0;
for (int num3: nums3)
{
for (int num4: nums4)
{
int s = num3 + num4;
auto it = sum.find(-s);
if (it != sum.end())
count += it->second; // it->second也可以写作sum[-s]
}
}
return count;
}
};
更简洁的写法：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>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> map;
for (int num1: nums1)
for (int num2: nums2)
map[num1 + num2] ++ ;
int count = 0;
for (int num3: nums3)
for (int num4: nums4)
{
int target = -(num3 + num4);
if (map.find(target) != map.end())
count += map[target];
}
return count;
}
};
383. 赎金信
注意，本题的题干中虽然强调了Each letter in magazine can only be used once in ransomNote，但这个条件在写代码时实际上并不需要考虑。这应该只是生成测试样例时需要遵守的规则。
本题用暴力做法也可以过，但暴力做法的代码写起来似乎还更麻烦一点。暴力做法就是两重for循环，若ransomNote中出现了magazine中出现过的字符，则从ransomNote中移除该字符，最后判断ransomNote的长度是否为0即可。暴力做法的代码可以参见代码随想录。
至于时间复杂度为O(n)的哈希解法，我在初次尝试中写的就已经很完美了。若想进一步优化，可以加上判断：若ransomNote的长度大于magazine的长度，则可以直接return false。若在遍历字符串时就对数组中元素的正负进行判断，那需要注意：只能在ransomNote中对数组中元素的正负进行判断，为负则说明赎金信中有magazine中没有的字符。若在magazine中对数组中元素的正负进行判断，可能存在问题：数组中的元素为正不一定代表赎金信中有magazine中没有的字符，可能仅仅是因为尚未遍历完成，数组中的元素还没被减到负数。因此，下面的代码是错误的：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int N[26];
if (ransomNote.size() > magazine.size()) return false;
for (char r: ransomNote)
N[r - 'a'] ++ ;
for (char m: magazine)
{
N[m - 'a'] -- ;
if (N[m - 'a'] > 0) return false;
}
return true;
}
};
可以通过测试样例轻而易举地看出上述解法的漏洞，比如
ransomNote =”aa”
magazine =”aab”
Output false
Expected true
而代码随想录上的哈希解法的代码是正确的。
若想避免上述问题，最直接的办法就是等到N数组中的元素全部计算完成后，另开一个循环来判断其中是否有为正的元素。
15. 三数之和
本题可以用哈希法做，但比较复杂。本题需要返回的三元组，其中的元素是数组中元素的值，而非下标。注意：三元组是去重的。本题相较于两数之和的难点就在于去重。
哈希法的大致思路：用两重for循环，第一重确定a，第二重确定b，然后看-(a + b)是否在map中出现过。但这里的难点在于：需要同时对a, b和c（-a - b）去重。去重的细节太多了，基本上都会遇到小问题，难以一次想周全。因此推荐使用更易于理解的双指针法。
双指针法的思路：使用双指针法之前需要对数组进行排序。for循环遍历数组，得到a；left指针从数组的第2个位置开始向后移动，得到b；right指针从数组的最后一个位置开始向前移动，得到c。若num[i] + num[left] + num[right] > 0，说明三数之和大了，i是固定的（for循环从头开始遍历），因此应当让right --。若num[i] + num[left] + num[right] < 0，说明三数之和小了，应该让其变大，则应当让left ++。若三数之和为0，则将三者放入二维数组res中。注意细节：去重。num[i], num[left], num[right]三个数都需要去重，因为res中不能有重复的三元组。
伪代码：（注：a = num[i], b = num[left], c = num[right]）
1 | vector<vector<int>> res; // 存储结果 |
细节：
如何对a去重：
if (i > 0 && nums[i] == nums[i - 1]) continue;如何对b和c去重：
1
2while (right > left && right[i] == right[i - 1]) right -- ; // 对c去重
while (right > left && left[i] == left[i + 1]) left ++ ; // 对b去重对b和c去重的代码放在哪里
必须先收获结果，再去重。否则若出现数组中全是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
40class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 用双指针算法前需要先排序
vector<vector<int>> res; // 二维数组，存放结果
// 三元组{a, b, c}，i指向a, left指向b, right指向c
// a = nums[i], b = nums[left], c = nums[right]
for (int i = 0; i < nums.size(); i ++ )
{
// 若最小的a都大于0，则三数之和不可能等于0，不需要继续循环，返回现有的res即可
if (nums[i] > 0) return res;
// 对a去重
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = nums.size() - 1;
while (left < right)
{
if (nums[i] + nums[left] + nums[right] > 0) right -- ;
else if (nums[i] + nums[left] + nums[right] < 0) left ++ ;
else
{
res.push_back({nums[i], nums[left], nums[right]}); // 收获结果
// 对b和c去重
while (left < right && nums[left] == nums[left + 1]) left ++ ;
while (left < right && nums[right] == nums[right - 1]) right -- ;
// 移动left和right指针
left ++ ;
right -- ;
}
}
}
return res;
}
};
18. 四数之和
和三数之和思路相同，但多一重for循环。共有i, j, left, right四个指针，前三者初始时分别指向数组的前三个元素，right指向数组最后一个元素。left和right向中心靠拢，使得nums[i] + nums[j] + nums[left] + nums[right] = target。
细节：剪枝和去重。
- 一级剪枝：不能延续三数之和的剪枝操作：
if(nums[i] > target) return res;。这没有考虑到数组中可能有负数的情况，若数组中有负数，几个元素相加是越加越小的，因此即使最小的数大于target，通过加上一些负数，四数之和依然可能为target。正确的剪枝操作应该为：if (nums[i] > target && nums[i] > 0 && target > 0) break;。其实这里写break（即最后返回）和写return res都是可以的，并不会影响运行结果。 - 二级剪枝：
if (nums[i] + nums[j] > target && nums[i] + nums[j] > 0 && target > 0) break;二级剪枝完成后只能写break，写return res会有几个测试样例无法通过。原因：一级剪枝条件时直接return res，相当于结束所有循环，返回结果，不会漏掉部分四元组；二级剪枝时直接return res，同样相当于结束所有循环，返回结果，此时就会漏掉部分四元组。正确的做法应该是结束第二重循环，继续进行第一重循环。
其实还有一个细节需要注意，在求四数之和nums[i] + nums[j] + nums[left] + nums[right]时，若四个数都是10亿，加起来就会超过int的限制（大约21亿），因此需要把四数之和转化为long类型：(long) nums[i] + nums[j] + nums[l] + nums[r] > target。如果不将int转换为long，会报错：整数溢出，同时有几个测试样例无法通过。代码如下所示：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
37class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
// a = i, b = j(i + 1), c = l(i + 2), d = r(nums.size() - 1)
for (int i = 0; i < nums.size(); i ++ )
{
if (nums[i] > target && target > 0 && nums[i] > 0) return res; // 一级剪枝
if (i > 0 && nums[i] == nums[i - 1]) continue; // 一级去重
for (int j = i + 1; j < nums.size(); j ++ )
{
if (nums[i] + nums[j] > target && target > 0 && nums[i] + nums[j] > 0) return res; // 二级剪枝
if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 二级去重
int l = j + 1, r = nums.size() - 1;
while (l < r)
{
if ((long) nums[i] + nums[j] + nums[l] + nums[r] > target) r -- ;
else if ((long) nums[i] + nums[j] + nums[l] + nums[r] < target) l ++ ;
else
{
res.push_back({nums[i], nums[j], nums[l], nums[r]});
// 对l和r去重
while (l < r && nums[l] == nums[l + 1]) l ++ ;
while (l < r && nums[r] == nums[r - 1]) r -- ;
l ++ ;
r -- ;
}
}
}
}
return res;
}
};
心得与备忘录
454.四数相加II
本题的大体思路？
遍历前两个数组A和B，将a + b的值存入map
再遍历后两个数组C和D，在map中查找-(c + d)的值为什么选择map做哈希？
因为不仅需要存储a + b的值，还需要存储这个值出现的次数(map[a + b] ++)，用于在4中统计元组的个数map中的key放什么？value放什么？
map中的key放a + b的值，map中的value放这个值出现的次数如何统计元组的个数？
count += map[-(c + d)]如何统计a和b的和出现的次数？
map[a + b] ++
383. 赎金信
代码随想录上的哈希解法不如我在初次尝试部分写的哈希解法简洁，而且代码随想录的哈希解法在颠倒遍历两个字符串的顺序时容易出错。本题的最佳解法是我在初次尝试部分写的第二个版本的代码。
15. 三数之和
- 采用双指针法，不要用哈希法，哈希法写起来复杂，去重麻烦、难以做剪枝操作，故效率显著低于双指针法
- 双指针法思路简单，但要注意去重的细节
- 排序的目的是方便剪枝，且一个三元组只会有唯一的顺序
- 双指针法只适用于返回的结果是数而不是索引的题目，因为双指针法使用前必须对数组进行排序，排序后索引会被打乱，因此返回的结果不能是索引。若两数之和要求返回的结果是数，那么也可以用双指针算法。这不禁让我思考，若本题要求返回的结果是索引，那么也只能用哈希法。但如果要求返回的结果是索引，那么就不需要有复杂的去重操作，因此实际上是简化了本题。
- 对于
nums[i]（即a）去重的代码，可以用if判断写：if (i > 0 && nums[i] == nums[i - 1]) continue;，也可以用while循环写：while (i < nums.size() && i > 0 && nums[i] == nums[i - 1]) i ++ ;。一般在写while循环时，都需要加上对数组索引不可越界的限制：i < nums.size()。如果出现报错：Runtime Error: AddressSanitizer，大概率是因为数组索引越界了，此时需要检查是否加上了限制条件i < nums.size()和i > 0。
18. 四数之和
- 本题思路和三数之和相同，但需要注意剪枝的细节
- 还需要注意在求四数之和时将int类型转换为long类型，避免整数溢出。
- 若采用双指针算法，三数之和的时间复杂度是
O(n^2)，四数之和的时间复杂度是O(n^3)。用暴力做法的时间复杂度则分别为O(n^3)和O(n^4)。 - 本题相比于四数相加，由于要考虑去重问题，所以更加复杂，因此无法（不推荐）使用哈希法，推荐使用双指针算法。
- 剪枝方面可以做进一步的优化，但属实没有必要。
- 本题写剪枝统一用break，不要用return res，以免方式意外的错误
- 本题如果有几个测试样例总是过不了，可以直接删去剪枝的代码，一般就可以通过了。剪枝是优化，即使不加，依然可以轻松通过。剪枝部分是易错点。
哈希表总结
- 哈希表的使用场景：快速判断一个元素是否在集合中出现过。
- 哈希的三重境界：普通数组->set->map。
- 目前哈希中用到的set和map实际上是unordered_set和unordered_map，相对于set和map中的另外两种数据结构（set, multiset, map, multimap），unordered_set和unordered_map的查询效率和增删效率都是最高的。选择set类型的三种数据结构时，若我们不需要数据有序，且需要去重，且希望效率高，则用unordered_set。选择map类型的三种数据结构时，若我们不需要key有序，且希望效率高，则用unordered_map。
- 遇到哈希问题时，首先想想能不能用数组做哈希（比如题目中提到字符串中全是小写英文字母，就果断用数组做哈希）。用数组做哈希最直接，运行速度也最快，用set做哈希速度更慢，但遇到大规模的索引，数组放不下时，只能用set。
- 什么时候用map做哈希？当对一个元素需要同时存储两个值时，就必须用map做哈希。这两个值一个作为key，一个作为value存入map中。key中一般存储的是元素的值（便于查询），value中可以存放元素的索引（如1. 两数之和），也可以存放元素出现的次数（如454.四数相加II）。
- map可以当作普通数组一样使用，忘了STL的用法可以复习知识部分。
- 哈希表部分的八道算法题，前六道都使用的是正统的哈希法，最后两道（三树之和&四数之和）并非不可以使用哈希法，但使用哈希法需要进行复杂的去重操作，代码容易写错，且运行效率低下，因此推荐使用双指针算法。
- 三数之和&四数之和的易错点在于剪枝和去重。每重for循环都需要剪枝和去重，while循环进行去重即可，但其实剪枝是一种优化，并不是必须的。但去重是必须的！