哈希表
赎金信（leetcode.383）
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
并不困难，因为字母都是小写的，那么可以定义一个hash[26]作为映射，先看看magazine中的库存有什么字符，然后遍历ransomNote，如果遍历完，字符数量有小于0出现，表示没有相应的字符，返回false
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {if (ransomNote.size() > magazine.size()) {return false;} // 可以先判断一下是否满足库存字符大于需要字符int hash[26] = {0};for(const auto& c : magazine){++hash[c - 'a'];}for(const auto& c : ransomNote){--hash[c - 'a'];if(hash[c - 'a'] < 0){return false;}}return true;}
};
三数之和（梦破碎的地方）leetcode.15
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
这题其实挺有难度的，而且哈希表不好求，还是来看一下思路：
索引不能相同，元素之和为0，而且组成的三元组不能重复；也就是说a+b+c=0，再进行遍历时候，a不可重复，b不可重复，那么c = -(a+b)自然不重复。
首先，我们需要对数组进行排序，使用sort对其进行升序排序，得到新的nums；开始遍历数组，先固定住其中一个i，然后再次进行遍历j,那么这里为了保证a不重复，那么就需要进行判断了，如果nums[i] == nums[i-1],这就说明a重复了，得跳过；后面开始找b，那么我们需要一个哈希表存放目标值c，因为通过b可以知道目标值c=-(a+b)，所以我们需要将目标值放入集合，如果后面遍历发现目标值就达到条件了，但是这里达到条件后需要注意细节了，因为b也有可能重复，所以说还需要进行判断，while(j < n-1 && nums[j] == nums[j+1]) ++j;如果目标数后面一位依然是目标数，那么就要跳过了；最后返回满足题目的所有三元组。
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result;std::sort(nums.begin(),nums.end());int n = nums.size();if(n < 3) return result;for(int i = 0; i < n; ++i){// 如果排好序的数组遍历到的当前数大于0,就退出了if(nums[i] > 0) break;// 如果遍历到的数和上一轮一样，也不行,因为要不重复// 上一轮已经选择了这个元素了if(i > 0 && nums[i] == nums[i-1]) continue;unordered_set<int> set_; // 存储第三个数for(int j = i+1; j < n; ++j){int target = -nums[i] - nums[j];if(set_.find(nums[j]) != set_.end()){result.push_back({nums[i], nums[j], target});while(j < n-1 && nums[j] == nums[j+1]) ++j;}set_.insert(target);}}return result;}
};
双指针法
大概思路差不多，也是先固定一个值，然后定义两个指针，一个left,一个right,可以通过判断三者之和sum，来调整双指针指向，如果大了，说明right指向太大，--right，小了，++left；如果满足条件，就说明找到目标的三元组了，找到后续需要再进行重复性判断的问题，外层循环已经解决了a的重复，需要对left、right进行重复性判断，通过while来实现，满足前提条件，left<right下，while(left < right && nums[left] == nums[left+1]),++left,如果没有重复，正常++left,--right。
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result;std::sort(nums.begin(),nums.end());int n = nums.size();if(n < 3) return result;for(int i = 0; i < n; ++i){if(nums[i] > 0) break;if(i > 0 && nums[i] == nums[i-1]) continue;int left = i+1, right = n-1;while(left < right){int sum = nums[i] + nums[left] + nums[right]; if(sum > 0) --right;else if(sum < 0) ++left;else{result.push_back({nums[i],nums[left],nums[right]});while(left < right && nums[left] == nums[left+1]) ++left; // 不写left < right 会出现索引越界错误while(left < right && nums[right] == nums[right-1]) --right;++left; // 正常情况--right;}}}return result;}
};
四数之和（leetcode.18）
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案
没啥，前面三数之和会了后，这题并无大问题
class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());vector<vector<int>> res;int n = nums.size();if(n < 4) return res;for(int i = 0; i < n; ++i){if(nums[i] > 0 && nums[i] > target) break;if(i > 0 && nums[i] == nums[i-1]) continue; // 保证a不重复for(int j = i+1; j < n; ++j){if(static_cast<long long>(nums[i] + nums[j]) > target && target > 0) break; if(j > i+1 && nums[j] == nums[j-1]) continue; // 保证b不重复int left = j+1, right = n-1;while(left < right){long long sum = static_cast<long long>(nums[i]) + nums[j] + nums[left] + nums[right];if(sum > target){--right;} else if(sum < target){++left;} else {res.push_back({nums[i],nums[j],nums[left],nums[right]});while(left < right && nums[left] == nums[left+1]) ++left;while(left < right && nums[right] == nums[right-1]) --right;++left;--right;}}}}return res;}
};