RY 's Blog

LeetCode:413. Arithmetic Slices

2019-06-04

413. Arithmetic Slices

这道题，简而言之，求数组里，等差序列的个数。

比如

1
2
3
A = [1, 2, 3, 4]
有3个等差数列
[1, 2, 3], [2, 3, 4], [1, 2, 3, 4]

题目没有说明A是等差数列，所以也要考虑A不是等差数列，但是其子数组是等差数列的情况。

1
2
3
4
5
6
7
8
9
10
11
A = [1, 3, 5, 7, 9, 15, 20, 25]
1, 3, 5

3, 5, 7
1, 3, 5, 7

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

15, 20, 25

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int numberOfArithmeticSlices(vector<int>& A) {
    int dp = 0;
    int sum = 0;

    for (int i = 2; i < A.size(); ++i) {
        if (A[i] - A[i-1] == A[i-1] - A[i-2])  {
           dp = 1+dp;
           sum += dp;
        } else {
           dp = 0;
        }
    }
    return sum;
}
Tags: Algorithm
← ReactNative开发-神器Reactoron 714. Best Time to Buy and Sell Stock with Transaction Fee →

scan qr code and share this article