Simple DP solution O(n)


  • 1
    P
    If A[i], A[i-1], and A[i-2] forms an Arithmetic slice, it can form more with number of slices at A[i-1]. For example, A = [1 2 3 4], at 4, [2 3 4] forms a slice, it can form more with number of slices formed at 3, which 1 ([1 2 3]). So, the number of slices can be formed at 4 is 2 ([2 3 4], [1 2 3 4]). In the end, add up all the numbers is the result.
    
    class Solution {
    public:
        int numberOfArithmeticSlices(vector<int>& A) {
            if (A.empty()) return 0;
            vector<int> vec(A.size(), 0);
            for (int i = 2; i < A.size(); ++i)
            {
                if ((A[i] - A[i - 1]) == (A[i - 1] - A[i - 2]))
                    vec[i] += vec[i - 1] + 1;
            }
    
            for (int i = 1; i < vec.size(); ++i)
                vec[i] += vec[i - 1];
    
            return vec.back();
        }
    };
    

Log in to reply
 

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