题目：454.四数相加Ⅱ
思路：
0.知道用map，但是map存啥
1.暴力法，四层循环遍历哈哈哈哈
2.分而治之，化繁为简，四个数组a,b,c,d分成两组，题目求符合要求的元祖个数，所以将a+b的值和出现次数存储，之后遍历查找c+d中0-（c+d）出现的次数，统计为结果
时间复杂度: O(n^2)
空间复杂度: O(n^2)，最坏情况下A和B的值各不相同，相加产生的数字个数为 n^2
坑：
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> map;
for(int i=0;i<nums1.size();i++){
for(int j=0; j<nums2.size();j++){
int sum=nums1[i]+nums2[j];
auto iter=map.find(sum);
if(iter!=map.end()){
(iter->second)++;
}else{
map.insert({sum,1});
}
}
}
//可优化为 范围for循环和 map[a+b]++;
//下标索引机制，使用下标访问不存在的元素时，会导致向map中添加该下标所对应的新元素``
int count=0;
for(int i=0;i<nums3.size();i++){
for(int j=0; j<nums4.size();j++){
int sum=nums3[i]+nums4[j];
if(map.find(0-sum)!=map.end()){
count+=map[0-sum];
}
}
}
return count;
}
};
补充：
map的操作
插入、查找、删除，遍历
插入
map<int,int> map
- pair
map.insert(pair<int,int>(1,2)); - make_pair
map.insert(make_pair<int,int>(1,3)); - value_type
map.insert(map<int,int>::value_type(2,3)); - []
map[3]=4 ; //插入key为3，value为4
在map中使用下标访问不存在的元素将导致在map容器中添加一个新的元素。
题目：383.赎金信
思路：
1.哈希数组，存储字符串中每个字母出现的次数，遍历第二个字符串时，--，如果有数组中有<0，则不能构成。
2.暴力法，
坑：
- 数组初始化错了
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
//string 可以使用下标访问和范围for循环
//缺少 判断两个字符串长度，大于直接false
if(ransomNote.size()>magazine.size())
return false;
int table[26]={0}; //报错，初始化{26,0}不对。
for(auto m:magazine){
table[m-'a']++;
}
for(auto r: ransomNote){
table[r-'a']--;
if(table[r-'a']<0)
return false;
}
return true;
}
};
补充：
string
访问string对象中的每一个元素
一个string对象表示一个字符序列，可以使用 范围for循环，
访问string对象中的单个字符
- 使用下标
- 使用迭代器
题目：15.三数之和
思路：
0.类似四数相加，分组为a+b和c，查找0-（a+b），使用两个map存储，一个存a,b ，一个存c,b 需要去重 看错了，是同一个数组内
- 暴力法 三层循环
- 哈希法，但是去重困难
- 三指针法，0,left,right、对应值相加，大了左移right，小了右移left 。难点也是去重 ，先排序就容易，因为目没要求返回下标，可以改变元素的位置
坑：
补充：
sort排序