C++ Solution 112 ms time, memory O(n^2)


  • 0
    S

    I start with dynamic version:

    map<long long, map<long long, long long>> need; // In need[NUM][diff] I remember how many arithmetic sequences (wich ends on NUM with diff) , I will get if my sequens will have NUM
    

    But I have Memory limit, so I try to store something only if I need it's in future. So I don't store any pairs of numbers, I store them only if I have number 2*A[i]-A[j]. Also I change map on vector, because I can remember only numbers from A.

    The Solution:

        int numberOfArithmeticSlices(vector<int>& A) {
            vector<unordered_map<int, int>> d(A.size()); // In d[i][diff] I remember how many arithmetic  sequences   length >= 2 (wich ends on A[i] with diff) , we have between A[0] and A[i] (including)
            int res = 0;
            unordered_set<int> s(A.begin(), A.end());
            for (int i = 0; i < A.size(); ++i) {   // we update d
                for (int j = 0; j < i; ++j) {      // we try to find pair to A[i]
                    long long diff = (long long)A[i] - A[j];
                    if (diff > INT_MAX || diff < INT_MIN) continue; // we don't need long long
                    int addon = d[j].count(diff) ? d[j][diff] : 0;  // it's how many arithmetic seq with last two:    A[j] and A[i]
                    res += addon;
                    if (s.count(A[i]+diff)) {   // do we need sequences with beside A[j], A[i] in future?
                        d[i][diff] += addon;  // sequences with length >= 3 with A[j] A[i]
                        d[i][diff]++;  // now sequence A[j] A[i] also need to be computed
                    }
                }
            }
            return res;
        }
    

Log in to reply
 

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