LeetCode 454 4Sum II

概述

https://leetcode.com/problems/4sum-ii/

哈希表记录两数之和

时间复杂度 O(n^2)

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int n = nums1.size();
        unordered_map<int, int> m1;
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < n; j ++) {
                m1[nums1[i]+nums2[j]] ++;
            }
        }
        unordered_map<int, int> m2;
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < n; j ++) {
                m2[nums3[i]+nums4[j]] ++;
            }
        }     
        int ans = 0;
        for (auto iter = m1.begin(); iter != m1.end(); iter ++) {
            ans += iter->second * m2[-iter->first];
        }
        return ans;
    }
};