C++ 3ms simple Math solution with Explanation


  • 0

    key point:
    For an arithmetic sequences consist by n number, it has (1 + n - 2) * (n - 2) / 2 slices in it.
    example 1,2,3,4,5,6
    1,2,3,4,5,6->1
    1,2,3,4,5;;2,3,4,5,6 -> 2
    1,2,3,4;;2,3,4,5;;3,4,5,6->3
    1,2,3;;2,3,4;;3,4,5;;4,5,6->4
    1 + 2 + 3 + 4 = (1 + (6-2)) * (6-2) / 2

    class Solution {
    public:
        int numberOfArithmeticSlices(vector<int>& A) {
            int res = 0, n = A.size(), l = 0;
            
            for (int i = 2; i < n;) {
                bool f = false; // indicate arithmetic sequences
                // find an arithmetic sequences index[l, i - 1];
                while (i < n && A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
                    i++;
                    f = true;
                }
                int len = i - l;
                // in an arithmetic sequences, there are (1 + len - 2 ) *  (len - 2) / 2 possible slices.
                res += f ? ((1 + len - 2) * (len - 2) / 2) : 0;
                l = i - 1;
                i++;
            }
            
            return res;
        }
    };
    

Log in to reply
 

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