[leetcode] 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.

---

  分析：题目翻译一下：一个数组，要求找间隔相同的子数组数量，要求每个子数组长度必须>=3并且必须相邻。

第一个思路，因为要累加计算，比如已经确定1，3，5满足要求，就继续判断下面的7和9，满足要求就+1。这个思想是以每个子数组的第一个元素考虑，时间复杂度是O(n^2)。代码如下：

class Solution {
       public int numberOfArithmeticSlices(int[] A) {
        int count = 0;
        for ( int i = 0 ; i < A.length - 2 ; i ++ ){
            int target = A[i+1]-A[i];
            for ( int j = i + 2 ; j < A.length ; j ++ ){
                if ( A[j] - A[j-1] == target ) count++;
                else break;
            }
        }
        return count;
    }
}

      运行时间1ms，击败100%的提交。时间已经非常好了，但是时间复杂度还不是O(n)，有没有办法降到最低呢？

---

思路二：上面我们考虑的是以每个子数组开头元素，这个思路下我们考虑每个子数组最后一个元素。这时就考虑使用动态规划。

1、维持一个dp数组，dp[i]表示以i位置元素结尾的满足条件的子数组的数量。

2、初始化，因为考虑末尾元素，所以dp[0]=dp[1]=0

3、状态转移方程：如果满足A[i]-A[i-1]==A[i-1]-A[i-2]，那么dp[i]=dp[i-1]+1。否则dp[i]=0。

代码如下：

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

    运行时间1ms。时间复杂度O(n)，空间复杂度O(n)。