leetcode 454 4Sum II

首先想到的是四维循环。。。 但很明显❎️

大部分算法都是将问题的规模变小，然后将小问题组合成为最后需要问题的解

将前两个 vector 中所有数字组合的和记录到一个哈希表中，然后在后两个 vector 中找是否有数字和哈希表中的数字成相反数就可以了

复杂度： 遍历两个 vector 复杂度是 \(N^2\) ,所以最后的复杂度也就是 \(O(n^2)\)

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int,int> mm;
        for(int i=0;i<A.size();i++){
            for(int j=0;j<B.size();j++){
                if(mm.find(A[i]+B[j])==mm.end()){
                    mm[A[i]+B[j]]=1;
                }else{
                    mm[A[i]+B[j]]++;
                }
            }
        }
        
        int cnt=0;
        for(int i=0;i<C.size();i++){
            for(int j=0;j<D.size();j++)
            {
                int target=-(C[i]+D[j]);
                if(mm.find(target)!=mm.end()){
                    cnt+=mm[target];
                }
            }
        }
        return cnt;
    }
};