413. Arithmetic Slices

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence: A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Example:

A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

解题思路为Dynamic Programming。

令dp[i]表示the number of arithmetic slices ends with A[i]。 如果A[i-2], A[i-1], A[i]是arithmetic，则

dp[i] = dp[i-1] + 1

因为所有以A[i-1]结尾的arithmetic slice加上A[i]都是arithmetic slice，然后再加上一个arithmetic slice：A[i-2], A[i-1], A[i]。

public class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        if(A == null || A.length < 3) return 0;
        int n = A.length;
        int[] dp = new int[n];
        int res = 0;
        for(int i = 2; i < n; i++) {
            if(A[i] - A[i-1] == A[i-1] - A[i-2]) dp[i] = dp[i-1] + 1;
            res += dp[i];
        }
        return res;
    }
}

注意到dp[i]只跟dp[i-1]有关，因此可以只用一个变量表示，space complexity缩减为O(1)。

public class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        if(A == null || A.length < 3) return 0;
        int n = A.length;
        int dp = 0;
        int res = 0;
        for(int i = 2; i < n; i++) {
            if(A[i] - A[i-1] == A[i-1] - A[i-2]) dp = dp + 1;
            else dp = 0;
            res += dp;
        }
        return res;
    }
}