454.四数相加II
先贴我的代码;
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int res = 0;
unordered_map<int,int> box12;
unordered_map<int,int> box34;
for(int a : nums1){
for(int b : nums2){
box12[a+b]++;
}
}
for(int a : nums3){
for(int b : nums4){
box34[a+b]++;
}
}
for(auto iter = box12.begin(); iter != box12.end(); iter++){
int val = iter->first;
auto iter34 = box34.find(-val);
if(iter34 != box34.end()) res += iter->second * iter34->second;
}
return res;做题心得：
? ? ? ? 我选择直接将12 和 34 俩个数组中的数进行相加并存进map，value 表示当前俩个数组能够组成 key 值有多少种不同的排列组合。
? ? ? ? 关键点，我最后遍历map的时候，返回的值是 res += iter12 * iter34，这是因为我直接把整个数组都计算过了，那么相乘就是其总共存在的当前对应值的解数量。
? ? ? ? 这里还有一个点需要注意：
? ? ? ? 需要注意 set? 和 map 的取值区别：
std::set
std::set 中的元素是键，因为它是一个集合，不包含重复元素。当使用?find?等方法在 std::set 中查找元素时，返回的迭代器指向的是元素本身。所以，你需要通过 * 操作符解引用迭代器来获取元素的值。
std::map:
std::map 中的元素是键值对，因此迭代器指向的是一个包含键值对的对象。你可以通过 -> 操作符来访问键值对中的成员，其中 first 是键，second 是值。
对于 std::map，迭代器的 -> 操作符已经被重载，允许你直接访问键值对的成员，而不需要显式地使用 * 操作符。这是因为 std::map 的迭代器是一个类对象，其 -> 操作符被定义为返回指向值部分的引用，这使得语法更加直观。它的迭代器直接提供了方便的访问方式，而不需要额外的解引用。
383. 赎金信
先贴我的代码：
bool canConstruct(string ransomNote, string magazine) {
int box[26] = {0};
if(ransomNote.size() > magazine.size()) return false;
for(char c : magazine){
box[c - 'a']++;
}
for(char c : ransomNote){
box[c -'a']--;
if(box[c-'a'] < 0) return false;
}
return true;
}解题心得：
? ? ? ? 对于这种问题，就是开辟一个数组空间，存放26个字母出现的次数，再用另外一个字符串里的字符去做对应的加加减减，而在此题中，如果信中的字符在杂志中没有或者用完了，那么对应的值肯定会小于0，通过这一点来判断是否有问题。
15. 三数之和
? ? ? ?先贴代码：
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
int l, r;
sort(nums.begin(),nums.end());
if(nums.size() == 0 || nums[0] > 0) return res;
for(int i = 0; i < nums.size()-2; i++){
if( i > 0 && nums[i] == nums[i-1]) continue;
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{
vector<int> val;
val.push_back(nums[i]);
val.push_back(nums[l]);
val.push_back(nums[r]);
res.push_back(val);
// 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;写题心得：
? ? ? ? 如何减枝，首先是当排完序后第一个值大于0，那肯定不会后面相加会得到 0；
? ? ? ? 排完序后，最外层 i 的循环，需要过滤掉与上一个 i-1 想同的值，因为 i-1 的答案一定是 i 所构成的答案的子集。
? ? ? ? 后面就没啥好说的了，记得在找到答案后，先对单边各自收缩，只要相等就收缩，直到不相同，还要对双边进行收缩。这里是为什么呢？假设不双边收缩只收缩一边，那么根本不可能会形成 == 0 的情况，因为等于 0 所对应的值已经收进答案中，并且重复的已经去除掉了，所以要想找下一个答案，肯定是俩边双向收缩。
? ? ? ? 还要关注一点就是如果 vector<vector<int>> 直接push元素，可以这么写：
? ? ? ? res。push_back（vector<int> {a,b,c,d...e}） 这么写更简洁。
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
int l, r;
sort(nums.begin(),nums.end());
for(int i = 0; i < nums.size(); i++){ // 这里原先写的 nums.size()-3
if(nums[i] > target && nums[i] >= 0) break;
if(i > 0 && nums[i-1] == nums[i]) continue;
for(int k = i + 1; k < nums.size(); k++){
if((nums[i] + nums[k]) > target && (nums[i] + nums[k]) >= 0) break;
if(k > i+1 && nums[k] == nums[k-1]) continue;
l = k+1, r = nums.size() - 1;
while( l < r){
if((long)nums[i] + nums[k] + nums[l] + nums[r] > target) r--;
else if((long)nums[i] + nums[k] + nums[l] + nums[r] < target) l++;
else{
res.push_back(vector<int>{nums[i],nums[k],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;
}解题心得：
? ? ? ? 不知道有没有人跟我一样，会追求代码一步都不要走错，所以在最开始遍历 i 以及 k 里面，我都给 nums.size() -3 和 -2，以至于使得代码不会做无用功，但是我没考虑到，Nums也有可能是空数组，如果我直接对空数组进行操作，导致的后果就是会有负数，会导致堆数据异常！！
（这边又细想了一下，如果 i 很极端遍历到最后一个元素，那么 k = i + 1 就会遍历超过此数组，但是并没有报错，是因为取值是合法的，再加上 k? < nums1.size()这个约束，则不可能执行下去，而我直接 Nums.size()-3则是非法操作，因为当size为0的时候，进行函数运算则不可能执行会导致报错）
? ? ? ? 其次减枝的时候要考虑负数的情况，因为不是为 0 。如果单纯的使得 nums【开头】 > target，则没考虑 target <?0 的情况,。
? ? ? ? 以及最后要扩充到 long ，不然会溢出。
关于 Nums.size() -3 合法性也可以按照下面的修改
if(nums.size() < 4) return res;
sort(nums.begin(),nums.end());
for(int i = 0; i < nums.size()-3; i++){ // 这里原先写的 nums.size()-3
if(nums[i] > target && nums[i] >= 0) break;
if(i > 0 && nums[i-1] == nums[i]) continue;
for(int k = i + 1; k < nums.size()-2; k++){只要先确认 nums的size > 4,那么下面关于 i 和 k 的范围取值 nums.size()就不会操作非法地址。