● 自己看到題目的第一想法

第454題.四數相加II

1. 方法：
   方法一： 暴力法 思路：

2. 注意：

3. 代碼：

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;}
};

4. 運行結果：
   

5. 方法：
   方法二： 哈希 思路：

   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;
   

6. 注意：

7. 代碼：

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. 方法： 哈希 思路：

   1. 定義一個數組大小為26，初始值為0；
   2. 遍歷magazine  將每個字符放入  數組中；
   3. 遍歷ransomNote   在其中查找 是否有magazine  中的字符
   4. 如果發現 ransomNote中存在某個英文字母   的統計次數大于 magazine 中該字母統計次數，則此時我們直接返回 false。
   

2. 注意：

3. 代碼：

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. 方法： 排序+雙指針：

2. 注意：

    1. 找到三數之和為0，必須先對left  與right去重后  left 與right 再分別向前  與后移動2. 需要分別對  i, left, right  去重
   

3. 代碼：

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. 四數之和

1. 方法： 排序+雙指針：

2. 注意： 一定要加(long),否則會溢出

3. 代碼：

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）的結果