c++ O(n^2) algorithm with unordered_map


  • 2
    N

    The algorithm is to hash the sum of each elements in A and B, then find whether opposite number for sum of elements in C and D occurs.
    The time complexity is O(n^2), space complexity is O(n)

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

  • 1

    It's O(n^2) space complexity.


  • 0
    A
    This post is deleted!

  • 0
    K

    Time Limit Exceeded


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.