Day6 | Part2
约 135 个字 74 行代码 预计阅读时间 1 分钟
第一想法直接暴力，时间\(O(n^4)\) → TLE,只过了39/132
利用哈希 → key:两个vector元素之和;value:对应出现的个数
- 遍历
nums1和nums2 统计里面的元素i+j出现的次数，放入map
- 再遍历
nums3和nums4，对-(k+l)进行计数
| int fourSumCount(vector<int>& nums1, vector<int>& nums2,
vector<int>& nums3, vector<int>& nums4) {
int cnt = 0;
unordered_map<int, int> map;
for (int i : nums1)
for (int j : nums2) map[i + j] ++;
for (int k : nums3)
for (int l : nums4) cnt += map[-(k + l)];
return cnt;
}
|
- 暴力做法 → \(O(n^2)\)
1
2
3
4
5
6
7
8
9
10
11
12
13 | bool canConstruct(string ransomNote, string magazine) {
for (int i = 0; i < magazine.length(); i ++) {
for (int j = 0; j < ransomNote.length(); j ++) {
if (magazine[i] == ransomNote[j]) {
ransomNote.erase(ransomNote.begin() + j); // 去除重复的
break;
}
}
}
if (ransomNote.length() == 0)
return true;
return false;
}
|
- 利用数组哈希 → \(O(n)\)
| bool canConstruct(string ransomNote, string magazine) {
int cnt[26] = {0};
for (auto c : magazine) cnt[c - 'a'] ++;
for (auto c : ransomNote)
if ( --cnt[c - 'a'] < 0) return false;
return true;
}
|
排序，利用双指针（注意去重） → 动图参考，（PS: 哈希解法）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | 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 (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
int l = i + 1, r = nums.size() - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum < 0) l ++;
else if (sum > 0) r --;
else {
res.push_back(vector<int>{nums[i], nums[l], nums[r]});
while(l < r && nums[l] == nums[l + 1]) l ++;
while(l < r && nums[r] == nums[r - 1]) r --;
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 | 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;// 去重
int l = j + 1, r = nums.size() - 1;
while (l < r) {
// 会溢出，需要转为long
auto sum = (long) nums[i] + nums[j] + nums[l] + nums[r];
if (sum > target) r --;
else if (sum < target) l ++;
else {
res.push_back(vector<int>{nums[i], nums[j], 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;
}
|
