454. 4Sum II

很可怕, 我的思維完全被僵化了, 我看到這題就想用老牌sum的方式去解, 發現再怎樣都不可能O(n³), 看討論有O(n²)的方法我傻眼

原來是我只要紀錄a, b的總和是多少, 並存在幾組

接下來對c, d的總和, 看能不能找到剛剛a,b所存的數, 就把a,b所有組合數加到結果裡

amazing

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> m;
        int res = 0;
        for(auto a: A){
            for(auto b: B){
                m[a+b]++;
            }
        }
        for(auto c: C){
            for(auto d:D){
                if(m.count(0-c-d)){
                    res+=m[0-c-d];
                }
            }
        }
        
       
        return res;
    }
};