day06
1. 454四数相加II
- 首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
- 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
- 定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
- 再遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
- 最后返回统计值 count 就可以了
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
std::unordered_map <int,int> map;
for(int a:A){
for(int b:B){
map[a+b]++;
}
}
int count=0;
for(int c:C){
for(int d:D){
if(map.find(0-(c+d))!=map.end()){
count+=map[0-(c+d)];
}
}
}
return count;
}
};
2. 383赎金信
类似day05中有效的字母异位词的思路。
1、首先遍历字符串ransomNote，遍历到一个字母便在数组num中对应位置-1（-1表示需要一个当前字母，-2表示需要两个当前字母…）。
2、遍历字符串magazine，遍历到一个字母便在数组num中对应位置+1（+1表示存在一个当前字母可以提供，+2表示存在两个当前字母可以提供…）。
3、遍历数组num，若存在num[i]<0，表示字符串ransomNote需要的当前字母在字符串magazine没有提供或提供的数量不够，则return false；否则return true。
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int num[26] = {0};
for (int i = 0; i < ransomNote.size(); i++) {
// 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
num[ransomNote[i] - 'a']--;
}
for (int i = 0; i < magazine.size(); i++) {
num[magazine[i] - 'a']++;
}
for (int i = 0; i < 26; i++) {
if(num[i]<0){
return false;
}
}
return true;
}
};
3.15三数之和
多指针法思路：
我们先将数组排序，直接 Arrays.sort() 解决，排序之后处理起来就很容易了。下面我们来看下三个指针的初始位置。
初始情况见上图，我们看当前情况，三数之和为 -3 ，很显然不是 0 ，那么我们应该怎么做呢？
我们设想一下，我们当前的三数之和为 -3 < 0 那么我们如果移动橙色指针的话则会让我们的三数之和变的更小，因为我们的数组是有序的，所以我们移动橙色指针（蓝色不动）时和会变小，如果移动蓝色指针（橙色不动）的话，三数之和则会变大，所以这种情况则需要向右移动我们的蓝色指针，找到三数之和等于 0 的情况进行保存，如果三数之和大于 0 的话，则需要移动橙色指针，途中有三数之和为 0 的情况则保存。直至蓝橙两指针相遇跳出该次循环，然后我们的绿指针右移一步，继续执行上诉步骤。但是这里我们需要注意的一个细节就是，我们需要去除相同三元组的情况，我们看下面的例子。
这里我们发现 0 - 1 + 1 = 0，当前情况是符合的，所以我们需要存入该三元组，存入后，蓝色指针向后移动一步，橙色指针向前移动一步，我们发现仍为 0 -1 + 1 = 0 仍然符合，但是如果继续存入该三元组的话则不符合题意，所以我们需要去重。这里可以借助HashSet但是效率太差，不推荐。这里我们可以使用 while 循环将蓝色指针移动到不和刚才元素相同的位置，也就是直接移动到元素 0 上，橙色指针同样也是。则是下面这种情况，这样我们就实现了去重，然后继续判断当前三数之和是否为 0 。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());//排序
//特殊情况处理
if(nums.size()<3||nums[0]>0){
return result;
}
//确定第一个数字
for(int i=0;i<nums.size()-2;i++){
int target=0-nums[i];
//去重，该逻辑确保在确定第一个数字（即 nums[i]）时，不会选取相同的数字作为新的起点。
if(i>0&&nums[i]==nums[i-1]){
continue;//跳过当前循环中剩余的代码，直接进入下一次循环
}
int l=i+1;
int r=nums.size()-1;
while(l<r){
//发现符合要求的值
if(nums[l]+nums[r]==target){
//保存
result.push_back(vector<int> {nums[i], nums[l], nums[r]});
//去重
while(l<r&&nums[l]==nums[l+1]) l++;
while(l<r&&nums[l]==nums[r-1]) r--;
l++;
r--;
}
else if(nums[l]+nums[r]>target){
r--;
}
else{
l++;
}
}
}
return result;
}
};
4. 18四数之和
类似三数之和的思路
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());//排序
//特殊情况处理
if(nums.size()<4){
return result;
}
//确定第一个数字
for(int i=0;i<nums.size()-3;i++){
//去重，该逻辑确保在确定第一个数字（即 nums[i]）时，不会选取相同的数字作为新的起点。
if(i>0&&nums[i]==nums[i-1]){
continue;//跳过当前循环中剩余的代码，直接进入下一次循环
}
//确定第二个数字
for(int j=i+1;j<nums.size()-2;j++){
//去重，注意j的条件
if(j>i+1&&nums[j]==nums[j-1]){
continue;
}
int l=j+1;
int r=nums.size()-1;
while(l<r){
long long sum=(long long)nums[i]+nums[j]+nums[l]+nums[r];//用int会溢出
//发现符合要求的值
if(sum==target){
//保存
result.push_back(vector<int> {nums[i],nums[j], nums[l], nums[r]});
//去重
while(l<r&&nums[l]==nums[l+1]) l++;
while(l<r&&nums[l]==nums[r-1]) r--;
l++;
r--;
}
else if(sum>target){
r--;
}
else{
l++;
}
}
}
}
return result;
}
};
