3ms, C++ concise greedy solution with O(n) time O(1) space


  • 0
    W
    class Solution {
        // Given an arithmetic slices with length n,
        // return how many substrings are also arithmetic.
        // Actually, it returns sum(1, ..., n-2)
        int count(int n) {
            if (n < 3) return 0;
            return ((n-1)*(n-2))>>1;
        }
    public:
        int numberOfArithmeticSlices(vector<int>& A) {
            int res = 0, n = A.size(), i = 0;
            
            while (i < n-2) {
                // Find the arithmetic slices from the current position i with maximum length.
                // If i >= n-2, there is no more arithmetic slice.
                int dis = A[i+1] - A[i], j = i+2;
                while(j < n && A[j] - A[j-1] == dis) j++;
                res += count(j-i);
                i = j-1;
            }
            return res;
        }
    };
    

Log in to reply
 

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