LeetCode 454. 四数加算II(C++)

タイトル:
整数を含む4つの配列リストA,B,C,Dが与えられ,A［i,j,k,l］＋B［j］＋C［k］＋D［l］＝0になるように,いくつの要素群(i,j,k,l)が計算されるかを示した.
問題を単純化するために,全てのA,B,C,Dは同じ長さNを有し,0≦N≦500であった.すべての整数の範囲は-228～228-1であり、最終的な結果は231-1を超えません.
例:

  :
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

  :
2

  :
      :
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

考え方:
本題では可能なシナリオの数だけを求め,具体的な数字の組合せを返す必要はないので,4数の和を2つの2数の和の和にゼロに変換することができる.AB配列のすべての組合せの和を保存することができ,異なる組合せ和の結果が同じである可能性があるため,mapストレージを採用し,CDの和を求め,mapでその負の数を探し,スキーム数を累積した.

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