Leetcode 413. Arithmetic Slices

Description

A sequence of numbers 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 sequences:

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 the 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.

Solution

题意是求一个数组的子数组是等差数列的个数。

等差数列,经典的dp问题,设dp[i]表示以i为终点下标,共有多少个等差数列子数组。

因此当A[i]-A[i-1] == A[i-1]-A[i-2],有dp[i] = dp[i - 1] + 1

然后发现dp可以用一个值就可以表示,将空间复杂度从O(n) -> O(1)。

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

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号