代码随想录算法训练营Day07 | 哈希表part02

Day06 哈希表part02

• 四数相加II
• • 哈希法
  • 赎金信
  • • 暴力枚举解法
    • 哈希法
    • 三数之和
    • • 双���针法

        当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

        四数相加II

        • 原文章链接：代码随想录

          哈希法

          1. 首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
          2. 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
          3. 定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
          4. 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
          5. 最后返回统计值 count 就可以了

          class Solution {public:    int fourSumCount(vector& A, vector& B, vector& C, vector& D) {        unordered_mapumap;//key:a+b的数值,value:a+b出现次数        //遍历A和B数组，统计两个数组元素之和，以及出现次数，放入umap        for(int a : A){            for(int b : B){                umap[a+b]++;            }        }        int count = 0;//统计a+b+c+d=0出现的次数        //遍历C和D数组，统计0-(c+d)在umap出现的次数        for(int c:C){            for(int d:D){                if(umap.find(0-(c+d)) != umap.end()){                    count += umap[0 - (c+d)];                }            }        }        return count;    }};

          时间复杂度: O(n^2)

          空间复杂度: O(n^2)，

          • != umap.end()：如果find函数找到了给定的键，它会返回一个指向该键值对的迭代器；如果没有找到，则返回umap.end()这个迭代器。因此，这个条件检查的是，查找的键是否存在于unordered_map中。

          • 本题乍眼一看好像和0015.三数之和 ，0018.四数之和 差不多，其实差很多。本题降低时间复杂度，使用哈希法会提高空间复杂度，但一般来说我们都是舍空间换时间， 工业开发也是这样。

            赎金信

            • 原文章链接： 代码随想录
              • 需要注意两点。

                第一点“为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。

                第二点 “你可以假设两个字符串均只含有小写字母。” 说明只有小写字母，

                暴力枚举解法

                class Solution {public:    bool canConstruct(string ransomNote, string magazine) {        for (int i = 0; i    
                时间复杂度: O(n^2)
                空间复杂度: O(1)
                  
                哈希法
                 
                题目说只有小写字母，那可以采用空间换取时间的哈希策略，用一个长度为26的数组来记录magazine里字母出现的次数。
                在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！
                class Solution {public:    bool canConstruct(string ransomNote, string magazine) {        //用一个26的数组，去记录magazine里边字母出现的次数        int record[26] = { 0 };        //对于异常的排除        if (ransomNote.size() > magazine.size())            return false;        for (int i = 0; i    
                时间复杂度: O(n)
                空间复杂度: O(1)
                  
                三数之和
                  

                • 这道题的难点就在于三元组是去重的

                  这道题用哈希法，去重的步骤太多，所以最好使用双指针法

                  1. 首先要将数组sort一下，
                  2. 然后要去重
                  3. 如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，right下标就应该向左移动
                  4. 如果 nums[i] + nums[left] + nums[right]
                  5. 注意第四步中遇到一个符合的三元组之后要对left和right进行去重，防止重复

                  双指针法

                  class Solution{public:    vector threeSum(vector& nums) {        vector result; //二维数组用来保存结果        sort(nums.begin(),nums.end());        for(int i = 0;i  0)                return result;            if(i>0&&nums[i] == nums[i-1])                continue;            int left = i+1;            int right = nums.size()-1;            while(right>left){              if(nums[i] + nums[left] + nums[right] > 0) right--;              else if(nums[i] + nums[left] + nums[right]  left && nums[right] == nums[right-1]) right--;                while(right > left && nums[left] == nums[left + 1]) left++;                //为了防止添加重复的三元组，需要将right指针向左移动，将left指针向右移动                //找到以后，双指针同时收缩，就跳出for循环了                right--;                left++;              }            }        }        return result;    }};

                  • 注意去重的时候

                    nums[i] = nums[i-1]和nums[i] = nums[i+1]的区别

                    我们选择使用nums[i] = nums[i-1]的时候才continue

                  • 如果用nums[i] = nums[i+1]，那我们就把三元组中出现重复元素的情况直接pass掉了。 例如{-1, -1 ,2} 这组数据，当遍历到第一个-1 的时候，判断下一个也是-1，那这组数据就pass了。

                    我们要做的是不能有重复的三元组，但三元组内的元素是可以重复的！