LeetCode

LeetCode-方法论-map&set-二

454,

#454 4Sum II

  • 描述

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    Input:
    A = [ 1, 2]
    B = [-2,-1]
    C = [-1, 2]
    D = [ 0, 2]

    Output:
    2

    Explanation:
    The two tuples are:
    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

  • 逻辑

    第一步：将A和B中元素的可能和作为key放入map1，value为这个和出现的频数。
第二步：将C和D中元素的可能和作为key放入map2，value为这个和出现的频数。
第三步：对于map1中的每个元素，在map2中查找这个元素对应的负数，如果找到，则结果中加上(这个元素的频数)×(map2中这个元素负数的频数)  DONE。

  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        // 第一步
        unordered_map<int, int> mp1;
        for (int a:A){
            for (int b:B)
                mp1[a+b]++;
        }

        // 第二步
        unordered_map<int, int> mp2;
        for (int c: C){
            for (int d: D)
                mp2[c+d]++;
        }
        
        // 第三步
        int res = 0;
        for (auto & itr : mp1){
            if (mp2.find(-(itr.first)) != mp2.end())
                res += (itr.second) * (mp2[-(itr.first)]);
        }

        return res;
    }

    敲黑板理清楚逻辑后再实现。