哈希表
用哈希表来统计两个字符串的每个字符数量。因为有26个字母，所以可以直接用大小为26的数组来记录。而不需要用哈希表容器。
1
2
3
4
5
6
7
8
9
10
11
12
| bool isAnagram(string s, string t)
{
int charCnt[26]{};
for (char c: s) charCnt[c - 'a']++;
for (char c: t) charCnt[c - 'a']--;
for (int i: charCnt)
if (i != 0) return false;
return true;
}
|
1
2
3
4
5
6
7
8
9
10
| bool isAnagram(string s, string t)
{
unordered_map<char, int> hashS, hashT;
for (char c: s) hashS[c]++;
for (char c: t) hashT[c]++;
return hashS == hashT;
}
|
哈希+排序
因为异位词的字母相同，排序后得到的值也是一样的，可以用它作为哈希表的键值。
哈希表的键值为排序后的字符串，值为异位词组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| vector<vector<string>> groupAnagrams(vector<string>& strs)
{
unordered_map<string, vector<string>> groups;
vector<vector<string>> res;
for (const string& str: strs)
{
string key = str;
sort(key.begin(), key.end());
groups[key].push_back(str);
}
for (pair<string, vector<string>> p: groups)
res.push_back(p.second);
return res;
}
|
哈希+计数
因为题目只有26个字母，所以可以用大小为26的数组来计数，把计数的数组作为哈希的键值。不过哈希默认不支持数组作为键值，所以得额外设计哈希函数。
类似于76. 最小覆盖子串，利用滑动窗口+哈希的方式去寻找覆盖子串。不同之处在于，这道题是寻找异位词，子串中不能包含多余的其他字符。所以需要额外排除有多余字符的子串。
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
| vector<int> findAnagrams(string s, string p)
{
int sHash[26] = {}, pHash[26] = {};
vector<int> res;
for (char c: p) pHash[c - 'a']++;
int len = 0;
for (int l = 0, r = 0; r < s.length(); r++)
{
sHash[s[r] - 'a']++;
if (sHash[s[r] - 'a'] <= pHash[s[r] - 'a']) len++;
while (l < s.length() && sHash[s[l] - 'a'] > pHash[s[l] - 'a'])
sHash[s[l++] - 'a']--;
while (r - l + 1 > p.length())
{
if (pHash[s[l] - 'a'] > 0)
len--;
sHash[s[l++] - 'a']--;
}
if (len == p.length())
res.push_back(l);
}
return res;
}
|
直接使用Set容器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| vector<int> intersection_set(vector<int>& nums1, vector<int>& nums2)
{
unordered_set<int> numSet(nums1.begin(), nums1.end());
unordered_set<int> interSet;
for (int num: nums1) numSet.insert(num);
for (int num: nums2)
{
if (numSet.find(num) != numSet.end())
interSet.insert(num);
}
vector<int> res(interSet.begin(), interSet.end());
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
|
vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{
unordered_map<int, int> numCnt1, numCnt2;
vector<int> interSet;
for (int num: nums1) numCnt1[num]++;
for (int num: nums2) numCnt2[num]++;
for (pair<int, int> p: numCnt1)
{
if (numCnt2[p.first] > 0)
interSet.push_back(p.first);
}
return interSet;
}
vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{
int hash1[1005] = {}, hash2[1005] = {};
vector<int> interSet;
for (int num: nums1) hash1[num]++;
for (int num: nums2) hash2[num]++;
for (int i = 0; i < 1000; i++)
{
if (hash1[i] > 0 && hash2[i] > 0)
interSet.push_back(i);
}
return interSet;
}
|
无限循环的条件是，得到的sum值在之前出现过。可以用Set容器来查重。
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
| int sumOfSqure(int n)
{
int sum = 0;
while (n != 0)
{
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
bool isHappy(int n)
{
unordered_set<int> numSet;
while (n != 1)
{
if (numSet.find(n) != numSet.end())
return false;
numSet.insert(n);
n = sumOfSqure(n);
}
return true;
}
|
这个题容易想到的方法就是暴力求解，但是时间复杂有\(O(n^2)\)。
题目的思路其实可以从找两个数加起来等于目标值，变成：遍历一个数组，判断数组中是否存在
target-nums[i] 。这样问题就转换为了利用哈希表的方法来查找，时间复杂度为\(O(n)\)。
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
|
vector<int> twoSum_compact(vector<int>& nums, int target)
{
unordered_map<int, int> numHash;
for (int i = 0; i < nums.size(); i++)
{
if (numHash.find(target - nums[i]) != numHash.end())
return {i, numHash[target - nums[i]]};
numHash[nums[i]] = i;
}
return {};
}
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_multimap<int, int> numHash;
vector<int> res(2);
for (int i = 0; i < nums.size(); i++)
numHash.insert(pair<int, int>(nums[i], i));
for (int& num : nums)
{
res[0] = numHash.find(num)->second;
numHash.erase(numHash.find(num));
if (numHash.find(target - num) != numHash.end())
{
res[1] = numHash.find(target - num)->second;
break;
}
}
return res;
}
|
分成两个部分，先计算1，2数组组合结果存入哈希表，然后利用哈希表来从3，4中判断是否有符合条件的。
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
|
int fourSumCount_saveMemory(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4)
{
int cnt = 0;
unordered_map<int, int> hash12;
for (int num1: nums1)
for (int num2: nums2)
hash12[num1 + num2]++;
for (int num3: nums3)
for (int num4: nums4)
cnt += hash12[0 - num3 - num4];
return cnt;
}
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4)
{
int cnt = 0;
unordered_map<int, int> hash12, hash34;
for (int num1: nums1)
for (int num2: nums2)
hash12[num1 + num2]++;
for (int num3: nums3)
for (int num4: nums4)
hash34[num3 + num4]++;
for (auto iter: hash12)
{
if (hash34.find(0 - iter.first) != hash34.end())
cnt += iter.second * hash34[0 - iter.first];
}
return cnt;
}
|
因为题目要求不能出现重复的组合，所以要涉及到元组三个数的去重问题。如果使用哈希表来解题，会不方便剪枝，最后时间和空间消耗都会非常大。最好的办法是使用双指针。
排序+双指针
先对数组排序。然后使用两个大循环，第一个循环负责遍历第一个数，第二个while循环使用左右双指针。因为是从小到大排序，所以如果三个数相加：
< 0：收缩左指针；
> 0：收缩右指针；
= 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
| vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] > 0) return res;
if (i > 0 && nums[i] == nums[i - 1]) continue;
int l = i + 1, r = nums.size() - 1;
while (l < r)
{
if (nums[i] + nums[l] + nums[r] > 0)
r--;
else if (nums[i] + nums[l] + nums[r] < 0)
l++;
else
{
res.push_back({nums[i], nums[l], nums[r]});
while (l < r && nums[r] == nums[r - 1]) r--;
while (l < r && nums[l] == nums[l + 1]) l++;
l++; r--;
}
}
}
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
| vector<vector<int>> threeSum_hash(vector<int>& nums)
{
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] > 0) return res;
if (i > 0 && nums[i] == nums[i - 1]) continue;
unordered_set<int> numSet;
for (int j = i + 1; j < nums.size(); j++)
{
if (j > i + 2 && nums[j] == nums[j - 1] && nums[j] == nums[j - 2])
continue;
int tmp = 0 - nums[i] - nums[j];
if (numSet.find(tmp) != numSet.end())
{
res.push_back({nums[i], nums[j], tmp});
numSet.erase(tmp);
}
else
numSet.insert(nums[j]);
}
}
return res;
}
|
类似 15. 三数之和 的思路，先使用一个循环确定第一个数，然后嵌套三数之和的循环。需要注意的是，题目数据范围非常大，四数相加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
37
38
| vector<vector<int>> fourSum(vector<int>& nums, int target)
{
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++)
{
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.size(); j++)
{
if (j > i + 1 && nums[j] == nums[j - 1])
continue;
long t = (long)target - nums[i] - nums[j];
int l = j + 1, r = nums.size() - 1;
while (l < r)
{
if (nums[l] + nums[r] < t)
l++;
else if (nums[l] + nums[r] > t)
r--;
else
{
res.push_back({nums[i], nums[j], nums[l], nums[r]});
while (l < r && nums[l + 1] == nums[l]) l++;
while (l < r && nums[r - 1] == nums[r]) r--;
l++; r--;
}
}
}
}
return res;
}
|