day7 哈希表2
454.四數(shù)相加II
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> umap;
int res = 0;
int n = nums1.size();
for (int num1: nums1) {
for (int num2: nums2) {
umap[num1 + num2] ++;
}
}
for (int num3: nums3) {
for (int num4: nums4) {
int target = - num3 - num4;
if (umap.find(target) != umap.end()) {
res += umap[target];
}
}
}
return res;
}
};
383. 贖金信
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<int, int> umap;
for (int ch: magazine) {
umap[ch] ++;
}
for (int ch: ransomNote) {
if (umap[ch] == 0) {
return false;
}
umap[ch] --;
}
return true;
}
};
字母數(shù)量有限憔杨，因此可以用數(shù)組表示槐壳，用數(shù)組做效率更高：
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
vector<int> vec(30, 0);
for (char ch: magazine) {
vec[ch -'a'] ++;
}
for (char ch: ransomNote) {
if (vec[ch-'a'] == 0) {
return false;
}
vec[ch-'a'] --;
}
return true;
}
};
15. 三數(shù)之和
菜狗哈希版：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
unordered_map<int, vector<int>> umap;
int n = nums.size();
for (int i = 0; i < n; i ++) {
umap[nums[i]].push_back(i);
}
for (int i = 0; i < n; i ++) {
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}
for (int j = i + 1; j < n; j ++) {
int target = - nums[i] - nums[j];
if (umap.find(target) != umap.end()) {
vector<int> vec = umap[target];
for (int index: vec) {
if (index > j) {
if (res.empty() || res.back() != vector<int>({nums[i], nums[j], nums[index]})) {
res.push_back({nums[i], nums[j], nums[index]});
}
}
}
}
}
}
return res;
}
};
有一些過濾條件沒有考慮到兆解，比方說第一個(gè)數(shù)如果>0片习，就可以return了。優(yōu)化哈希版不寫了式矫，快不了多少。
雙指針版：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
int n = nums.size();
for (int i = 0; i < n; i ++) {
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}
if (nums[i] > 0) {
break;
}
int left = i + 1;
int right = n - 1;
while (left < right) {
int num = nums[i] + nums[left] + nums[right];
if (num == 0) {
res.push_back(vector<int>({nums[i], nums[left], nums[right]}));
while (left < right && nums[left+1] == nums[left]) {
left ++;
}
while (left < right && nums[right-1] == nums[right]) {
right --;
}
left ++;
right --;
}
else if (num > 0) {
right --;
}
else {
left ++;
}
}
}
return res;
}
};
18. 四數(shù)之和
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
unordered_map<int, vector<vector<int>>> umap;
int n = nums.size();
for (int i = 0; i < n; i ++) {
for (int j = i + 1; j < n; j ++) {
int num = nums[i] + nums[j];
if (umap[num].empty()) {
umap[num].push_back({i, j});
}
else {
int index1 = umap[num].back()[0];
int index2 = umap[num].back()[1];
if (nums[index1] == nums[i] || nums[index2] == nums[j]) {
umap[num].pop_back();
}
umap[num].push_back({i, j});
}
}
}
for (int i = 0; i < n; i ++) {
if (nums[i] > target && nums[i] > 0) {
break;
}
if (nums[n-1] == 1000000000 && nums[n-2] == -1000000000) {
break;
}
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}
for (int j = i + 1; j < n; j ++) {
if (j > i + 1 && nums[j] == nums[j-1]) {
continue;
}
int num = nums[i] + nums[j];
if (umap.find((long)target - num) != umap.end()) {
cout << umap[(long)target-num].size() << endl;
for (auto vec: umap[(long)target - num]) {
int p = vec[0];
int q = vec[1];
if (p > j) {
res.push_back({nums[i], nums[j], nums[p], nums[q]});
}
}
}
}
}
return res;
}
};
啥垃圾題耙鄹采转？一天的好心情都被他搞沒了，溢出溢出溢出煩死了瞬痘，按照測(cè)試用例加了個(gè)break故慈，不看了，就這么著吧框全，煩死了
