LeetCode 454

概述

• https://leetcode-cn.com/problems/4sum-ii/
• 给定四个数组，从四个数组中各选一个，相加等于0
• 返回可选的组合的个数

思路

• 四个不同的数组中选，所以是各自独立的

• 返回可选的组合的个数，只需进行记录即可

• 综上，可以使用哈希法。考虑到四个数组，如果暴力求解大概率是超时，所以我们将两个数组的组合情况保存起来，再循环解决

  class Solution {
  public:
      int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
          unordered_map<int,int> mp1;
          for(int a:nums1){
              for(int b:nums2){
                  mp1[a+b]++;		//先记录两个数组的所有情况，因为最终结果只要数量，所以只要记录可以组合的值的数量即可
              }
          }
         // unordered_map<int,int> mp2;
         int count=0;
          for(int a:nums3){
              for(int b:nums4){	//另外两个数组排列组合
                  if(mp1.find(0-(a+b))!=mp1.end()){	//找期望有的值	
                      count+=mp1[0-(a+b)];
                  }
              }
          }
          return count;
   
      }
  };