● 自己看到题目的第一想法
第454题.四数相加II
-
方法：
方法一： 暴力法 思路： -
注意：
-
代码：
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int res = 0;
for(int i=0;i<nums1.size();i++){
for(int j = 0; j<nums2.size();j++){
for(int m = 0; m<nums3.size();m++ ){
for(int n = 0; n<nums4.size(); n++){
if(nums1[i]+nums2[j]+nums3[m]+nums4[n] == 0){
res++ ;
}
}
}
}
}
return res;
}
};
-
运行结果：
-
方法：
方法二： 哈希 思路：1. 定义unprdered_map<int, int>map; //key指两数之和， value指两数之和出现的次数 2. 将nums1与nums2之和放入map中； 3. 求nums3与nums4之和， 4. 在map中查找 -（nums3+nums4），若能找到则输出res+=map[-(nums3+nums4)] 5. 最终返回 res; -
注意：
-
代码：
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++){
map[nums1[i]+nums2[j] ]++;
}
}
int res= 0;
for(int k = 0; k<nums3.size(); k++){
for(int l = 0; l< nums4.size(); l++){
if(map.find(-(nums3[k]+nums4[l])) !=map.end()){
res += map[-(nums3[k]+nums4[l])];
// cout<<res<<endl;
}
}
}
return res;
}
};
383. 赎金信
-
方法： 哈希 思路：
1. 定义一个数组大小为26，初始值为0； 2. 遍历magazine 将每个字符放入 数组中； 3. 遍历ransomNote 在其中查找 是否有magazine 中的字符 4. 如果发现 ransomNote中存在某个英文字母 的统计次数大于 magazine 中该字母统计次数，则此时我们直接返回 false。 -
注意：
-
代码：
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
vector<int>record(26,0);
for(auto& i: magazine){
record[i-'a']++;
}
for(char i =0; i<ransomNote.size(); i++){
record[ransomNote[i]-'a']--;
if(record[ransomNote[i]- 'a'] < 0){
return false;
}
}
return true;
}
};
15. 三数之和
去重的代码：暴力法：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>>res;
for(int i=0;i<nums.size(); i++){
for(int j=i+1; j<nums.size(); j++){
for(int k=j+1; k<nums.size(); k++){
if(nums[i]+nums[j]+nums[k]==0){
vector<int>n ={nums[i], nums[j], nums[k]};
res.push_back(n);
}
}
}
}
return res;
}
};
- 方法： 排序+双指针：
-
注意：
1. 找到三数之和为0，必须先对left 与right去重后 left 与right 再分别向前 与后移动 2. 需要分别对 i, left, right 去重 -
代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>>res;
sort(nums.begin(), nums.end());
for(int i=0; i<nums.size(); i++){
if(i>0 && nums[i]==nums[i-1]){continue;}
// if (nums[i] > 0) {
// return res;
// }
int left= i+1;
int right =nums.size()-1;
while(left<right){
if(nums[left]+nums[right]+nums[i]<0){
left++;
}else if(nums[left]+nums[right]+nums[i]>0){
right--;
}else{
res.push_back(vector<int>{nums[i], nums[left], nums[right]});
// left++;
// right--;
while(left<right && nums[left]== nums[left+1]){left++;}
while(left<right && nums[right] == nums[right-1]){right--;}
left++;
right--;
}
}
}
return res;
}
};
18. 四数之和
-
方法： 排序+双指针：
-
注意： 一定要加(long),否则会溢出
-
代码：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>>res;
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; } //去重
for(int j=i+1; j<nums.size(); j++){
if(nums[i]+nums[j]>target && nums[i]+nums[j]>=0){break;} //二级剪枝
if(j>i+1 && nums[j]==nums[j-1]){continue;} //去重
int left= j+1;
int right = nums.size()-1;
while(left<right){
if((long)nums[left]+nums[right]+nums[i]+nums[j]<target){left++;}
else if((long)nums[left]+nums[right]+nums[i]+nums[j]>target){right--;}
else{
res.push_back(vector<int>{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;
}
};
没有加（long）的结果
