One pass Solution (C++)


  • 0

    My idea is finding longest arithmetic slices that has length larger than 3 from the beginning. Each longest slice with length n contains (n-2)*(n-1)/2 valid slices.

    class Solution {
    public:
        int numberOfArithmeticSlices(vector<int>& A) {
            auto s = A.begin(), e = s;
            int sum = 0;
            while (e != A.end() && e + 1 != A.end()) {
                int diff = *++e - *s;
                while (e != A.end() && *(e) - *(e - 1) == diff) e++;
                if (e - s > 2) {
                    sum += (e - s - 1) * (e - s - 2) / 2;
                }
                s = --e;
            }
            return sum;
        }
    };
    

Log in to reply
 

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