王烨雄镇江关键字优化品牌

题目:

454. 四数相加 II - 力扣（LeetCode）

思路:

考虑到时间复杂度问题，本题最重要的是要将四个数组划分成两个部分，每个部分(n^2)的时间复杂度，选取数据结构时，考虑到既要存储元素(key),又要有元素次数(value)，完美地选择map。

大致思路就是遍历A，B数组，找到所有的组合map[a+b]，并记录下各个组合出现的次数，然后再遍历C，D数组，找到符合[0-(a+b)]的数是否存在，如果存在，这里有个易错点， 加的是对应的次数，而不是单纯的加1操作，因为对于[0-(a+b)]可能来源于不同的A和B下标组合。

代码：

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map< int , int >map;for(int a:nums1){for(int b:nums2){map[a+b]++;//进行填数}}  int count = 0;for(int c:nums3){for(int d:nums4){if(map.find(0-(c+d)) != map.end())//此数存在匹配count+=map[0-(c+d)];}}  return count;}
};