Help!Got MLE using unordered_map and TLE using map!


  • 0
    B

    I got TLE when using map

    class Solution {
    public:
        typedef long long ll;
        int numberOfArithmeticSlices(vector<int>& A) {
            int sz = A.size();
            vector<map<ll, int> >dp(sz);
            int ans = 0;
            int tmp;
            for(int i = 1; i < sz; ++i){
                for(int j = 0; j < i; ++j){
                    ll dif = (ll)A[i] - (ll)A[j];
                    tmp = dp[j][dif];
                    dp[i][dif] += tmp + 1;
                    ans += tmp;
                 }    
            }
            return ans;
        }
    };
    

    And when I use unordered_map, I got MLE on the same case.
    However, if I add dp[j].count(dif) before I visit dp[j][dif], then Accepted....The code is below.

    class Solution {
    public:
        typedef long long ll;
        int numberOfArithmeticSlices(vector<int>& A) {
            int sz = A.size();
            vector<map<ll, int> >dp(sz);
            int ans = 0;
            int tmp;
            for(int i = 1; i < sz; ++i){
                for(int j = 0; j < i; ++j){
                    ll dif = (ll)A[i] - (ll)A[j];
                    tmp = dp[j].count(dif)? dp[j][dif]:0;
                    dp[i][dif] += tmp + 1;
                    ans += tmp;
                }
            }
            return ans;
        }
    };
    

    I am confused!Help!


Log in to reply
 

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