day7
454.四数相加 II
题目链接：454.四数相加 II
解题思路：
通过map使用哈希表进行计算，先存储前两个到一个哈希表中，然后寻找剩余两个之和是否满足题目条件，注意一些小问题：count应该是map中的键值，
C++中哈希表map的写法
unordered_map<int,int> map;
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> map;
int count= 0;
for( int num1:nums1 ){
for( int num2:nums2 ){
map[num1+num2]++;
}
}
for( int num3:nums3 ){
for( int num4:nums4 ){
int target = 0 - (num3+num4);
if( map.find(target) != map.end()){
// 第一次写的时候map[num3+num4]，注意区别，寻找的是target
count += map[target];
}
}
}
return count;
}
};
383.赎金信
题目链接：383.赎金信
解题思路：通过数组创建哈希表，参考异位词的方法
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
// 数组作为哈希表 我的写法
// int record[26]={0};
// for( int i = 0; i < ransomNote.size();i++){
// record[ransomNote[i]-'a']++;
// }
// for (int i = 0; i < magazine.size(); i++){
// if( record[magazine[i]-'a'] != 0){
// record[magazine[i]-'a']--;
// }
// }
// int total = 0;
// for ( int i = 0; i<26;i++){
// if (record[i]==0){
// total++;
// }
// }
// if (total == 26){
// return true;
// }
// return false;
//数组作为哈西表 官方写法
//时间：O(n)
//空间：O(1)
int record[26] = {0};
if ( ransomNote.size() > magazine.size() ){
return false;
}
for (int i = 0; i < magazine.size(); i++){
record[magazine[i]-'a']++;
}
for( int i = 0; i < ransomNote.size();i++){
record[ransomNote[i]-'a']--;
if (record[ransomNote[i]-'a'] < 0 ){
return false;
}
}
return true;
}
};
15.三数之和
题目链接：15.三数之和
题目思路：分为双指针和哈希两种方法，第一次使用双指针方法，具体解题思路见code
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//定义一个二维数组
vector<vector<int>> result;
// 将原数组排序
sort( nums.begin(),nums.end());
// 开始遍历
for ( int i = 0; i < nums.size(); i++){
// 如果第一个元素都>0 直接return
if ( nums[i] > 0 ){
return result;
}
// 第一个元素去重
if ( i > 0 && nums[i] == nums[i-1] ) continue;
// 开始双指针遍历
int left = i+1;
int right = nums.size() - 1;
// 循环揪出来result
while( left < right ){
// 总和>0
if (( nums[i] + nums[left] + nums[right]) > 0){
right--;
}
// 总和<0
else if (( nums[i] + nums[left] + nums[right]) < 0){
left++;
}
// 揪出元素
else{
result.push_back(vector<int>{nums[i], nums[left], nums[right]});
// 第三个元素去重
while (left < right && nums[right]==nums[right-1]){
right--;
}
// 第二个元素去重
while (left < right && nums[left]==nums[left+1]){
left++;
}
//找到答案移动双指针
left++;
right--;
}
}
}
return result;
}
};
18.四数之和
题目链接：18. 四数之和
解题思路：和三数之和的原理一样，使用双指针方法，只不过这里用了两层循环，同时要注意剪枝操作的时候的小细节，其他就是写代码的问题。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
// 创建二维数组
vector<vector<int>> result;
// 对原数组进行排序
sort( nums.begin(), nums.end());
// 第一层遍历 第一个元素
for ( int i = 0; i < nums.size(); i++){
// 剪枝操作
if ( nums[i] > target && nums[i] >= 0) break;
// 去重操作
if ( i > 0 && nums[i] == nums[i-1] ) continue;// 这里i>0必须在前面
// 第二层遍历 第二个元素
for ( int t = i+1; t < nums.size(); t++){ //注意细节，这里是t++ 开始写的i++
// 剪枝操作
if ( nums[i]+nums[t] > target && nums[i]+nums[t] >= 0) break;
// 去重操作
if ( t > i+1 && nums[t] == nums[t-1]) continue;
int left = t+1;
int right = nums.size()-1;
while( left < right){
if ((long) nums[i] + nums[t] + nums[left] + nums[right] > target) right--;
else if ((long) nums[i] + nums[t] + nums[left] + nums[right] < target) left++;
else{
result.push_back(vector<int>{nums[i] , nums[t] , nums[left] , nums[right]});
while( left < right && nums[right]==nums[right-1]) right--;
while( left < right && nums[left]==nums[left+1]) left++;
// 找到答案回收双指针
left++;
right--;
}
}
}
}
return result;
}
};