代码随想录算法训练营第七天

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

第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;
   }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4. 运行结果：
   

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

   1. 定义unprdered_mapmap;  //key指两数之和，  value指两数之和出现的次数
   2. 将nums1与nums2之和放入map中；
   3. 求nums3与nums4之和，
   4. 在map中查找 -（nums3+nums4），若能找到则输出res+=map[-(nums3+nums4)]
   5. 最终返回 res;
   1
   2
   3
   4
   5

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<
               }
           }
       }
       return res;
   }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

383. 赎金信

1. 方法： 哈希 思路：

   1. 定义一个数组大小为26，初始值为0；
   2. 遍历magazine  将每个字符放入  数组中；
   3. 遍历ransomNote   在其中查找 是否有magazine  中的字符
   4. 如果发现 ransomNote中存在某个英文字母   的统计次数大于 magazine 中该字母统计次数，则此时我们直接返回 false。
   1
   2
   3
   4

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1. 方法： 排序+双指针：

2. 注意：

    1. 找到三数之和为0，必须先对left  与right去重后  left 与right 再分别向前  与后移动
    2. 需要分别对  i, left, right  去重
   1
   2

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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;
   }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

没有加（long）的结果