四数相加II题型

http://学透哈希表，map使用有技巧！LeetCode：454.四数相加II

①为什么想到用哈希表?为什么是用map?
因为我们是用c+d去寻找有没有哪个a+b与之相加等于0，所以是寻找某值是否出现过，所以用哈希表。
因为是统计有多少个相加等于0的，所以需要统计a+b的次数，比如c+d=2，那需要a+b=-2，可能a+b=-2有3个，那么每个与c+d都可以与之为题目要求的一组结果啊，所以要一个值记录a+b的和，一个值记录a+b有多少个或者说出现了多少次，所以用map。
②为啥把for循环a+b放map里再for循环c+d去map里找是否存在对应的a+b，为什么不for循环a，再for循环b+c+d?
for循环a+b为n的平方，for循环c+d也是n的平方，那么相加起来时间复杂度就是N的平方。
如果是for循环a为n，for循环b+c+d是n的三次方，那么相加就是N的三次方了，所以时间复杂度就高了。
③整体思路，
定义一个map，key存放a+b的和,value存放这个和出现的次数。
for循环统计a+b，并且存放于map中，再for循环c+d，，并且去map中寻找0-(c+d)是否出现过，出现过则count+=value。
跟有效的异位词有点一样，思路都是 : 循环某组元素然后把它存放到哈希表中，然后再去循环另一组元素并且去哈希表中查找对应元素是否出现过。
④大致代码
unordered_mapmap;
      for(int a:nums1){
          for(int b:nums2){
              map[a+b]++;
          }
         }
      int count=0;
      for(int c:nums3){
          for(int d:nums4){
              int s=0-(c+d);
              if(map.find(s)!=map.end()){
                  count+=map[s];
              }
          }
      }
      return count;

赎金信题型

我刚开始的想法是，因为要存储两个值，一个是字母一个是字母出现的次数，所以用map，先遍历杂志字符串，同时存进map中，然后再遍历赎金信字符串，并且查看map是否有对应元素，如果无则返回false，如果有则次数减减，当减为0时则删除掉。
因为要存储两个值，脑袋一下子硬化了觉得只能用map，哎呀数组其实也是可以表达出两个值的存储的呀，比如a[i]=b，a[i]可以表示字母，b可以表示此字母出现的次数呀，我好笨啊，然后因为只是小写字母，所以值不多可以用数组呀。

这道题目和242.有效的字母异位词 (opens new window)很像，242.有效的字母异位词 (opens new window)相当于求 字符串a 和 字符串b 是否可以相互组成 ，而这道题目是求 字符串a能否组成字符串b，而不用管字符串b 能不能组成字符串a。

大致思路，用数组，定义一个长度26的数组，注意其中每一个均等于0，注意要是赎金字符串长度长于杂志字符串则肯定返回false，注意杂志字符串每个字母只能用一次。
然后遍历杂志字符串，将遍历的字母对应到数组++，然后再遍历赎金字符串，将遍历的字母对应到数组--，然后如果哪个元素<0，则返回false。

大致代码套路，
int res[26]={0};
     if(ransomNote.size()>magazine.size()){
         return false;
     }
     for(int i=0;i
         res[magazine[i]-'a']++;
     }
     for(int i=0;i
         res[ransomNote[i]-'a']--;
         if(res[ransomNote[i]-'a']<0){
             return false;
         }
     }
     return true;