A simple C++ solution with a math trick


  • 0
    S

    Key idea: try to find the arithmetic slice as long as possible and then build sub-slices from it

    class Solution {
    public:
        int numberOfArithmeticSlices(vector<int>& A) {
            if (A.size() < 3u)
                return 0;
            auto num = 0;
            // 1. find the length of each longest arithmetic sequences
            // For example: 1, 2, 3, 4, 7, 10 -> two sequences [1, 2, 3, 4] and [4, 7, 10] -> length: 4 and 3
            // 2. for a arithmetric sequence of length n, the number of length k <= n slice is n - k + 1
            // The total number of slices is n - 2 + n - 3 + ... + 1 = (n - 1)*(n-2)/2
            int length = 2;
            int diffOfSequence = A[1] - A[0];
            for (decltype(A.size()) i = 2; i < A.size(); i++){
                auto d = A[i] - A[i - 1];
                if (d == diffOfSequence)
                    length++;
                else{
                    diffOfSequence = d; // a new sequence
                    if (length >= 3)
                        num += (length - 1)*(length-2)/2;
                    length = 2;
                }
            }
            if (length >= 3) // the last sequence
                num += (length - 1)*(length-2)/2;
                
            return num;
        }
    };

Log in to reply
 

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