C++_DP_Accepted


  • 9
    class Solution {
    public:
    int numberOfArithmeticSlices(vector<int>& A) {
        if(A.empty()) return 0;
        vector<unordered_map<int,int>> dp(A.size());//[index, [difference, count]]
        
        int res = 0;
        for(int i = 0; i < A.size(); ++i){
            for(int j = 0; j < i; ++j){
                if((long)A[i] - (long)A[j] > INT_MAX || (long)A[i] - (long)A[j] < INT_MIN) continue;// do not ignore this step, it will help you save time & space to pass OJ.
                int dif = A[i] - A[j];
                dp[i][dif] += 1;
                if(dp[j].find(dif) != dp[j].end()){
                    dp[i][dif] += dp[j][dif];
                    res += dp[j][dif];
                }
            }
        }
        return res;
    }
    };

  • 0
    F

    I just test your code online, it gets TLE.


  • 1

    @FunYuCode Hi, thank u for your reply. I made a little revision of my code, and now I think it could be accepted by OJ.
    It's tricky if I delete if(dp[i].find(dif) == dp[i].end()){dp[i][dif] = 0;}, it is probably due to the initialization of unordered_map in Cpp.

    0_1479318484461_26ABF126-0448-4F16-A96F-243494483A6B.png


  • 0

Log in to reply
 

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