simple C++ with explanation


  • 0

    The key point to catch is to get the same difference counts then the problem becomes given N integers, how many ways you can slice.

    For example:
    A = [1, 2, 3,], difference_count = 2
    A = [1, 2, 3, 4], difference_count = 3
    A = [1, 2, 3, 4, 5], difference_count = 4

    Slice ways:
    count(2) = 1 (1 slice for length 2)
    count(3) = 2 + 1 (2 slice for length 2 + 1 slice for length 3)
    count(4) = 3 + 2 + 1
    count(n) = n-1 + n-2 + ... 1 = n * (n-1) / 2

    Then just iterate through and calculate the difference counts.

    int numberOfArithmeticSlices(vector<int>& A) {
        if (A.size() < 3) return 0;
        int last_diff = A[1] - A[0], same_counts = 0, slices = 0;
        for (int i = 2; i < A.size(); ++i) {
            if (A[i] - A[i-1] == last_diff)
                same_counts++;
            else {
                slices += (same_counts+1) * (same_counts) / 2;
                same_counts = 0;
                last_diff = A[i] - A[i-1];
            }
        }
        slices += (same_counts+1) * (same_counts) / 2;
        return slices;
    }
    

Log in to reply
 

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