Simple C++ O(n) time O(1) space solution


  • 0
    Y

    core idea is to find the each arithmetic segment, for each segment simply compute the number of sub arrays, for example if an arithmetic segment with length of 5, then the number of sub array is 6 (1-(5), 2-(4), 3-(3)), one with length 5, 2 with length 4, 3 with length 3. In the for loop accumulate the number of sub array, or you can also compute the number of array after the end of the each segment with formula (1+n)*n/2

    int numberOfArithmeticSlices(vector<int>& A) {
            int res = 0, count = 2, current = 0;
            if(A.size() < 3)return 0;
            for(int i = 2; i < A.size();i++)
            {
                if(A[i] - A[i-1] != A[i-1] - A[i-2])
                {
                    count = 2;
                    current = 0;
                }
                else
                    count++;
                if(count >=3)
                    res += ++current;
            }
            return res;
        }

Log in to reply
 

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