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

題目看起來 說明不少. 要我們切 數. 就是說要找長度3 以上的子等差數列
舉例來說,

[1,2,3]  的長度3 以上的等差數列有 :[1,2,3]

[1,2,3,4]  的長度3 以上的等差數列有 :[1,2,3], [2,3,4],[1,2,3,4]

[1,2,3,4,5]  的長度3 以上的等差數列有 :
[1,2,3], [2,3,4],[3,4,5],[1,2,3,4],[2,3,4,5],[1,2,3,4,5]

找到特徵了!

長度3的等差數列有 1              個子數列
長度4的等差數列有 1+2 = 3   個子數列
長度5的等差數列有 1+2+3=6 個子數列

這裡還需要考慮到 [1,2,3,4,6,7,8] 這種例子, 我們可以把這例子想成子等差數列個數 [1,2,3,4] + [6,7,8] => 3 + 1 = 4


line 5: 小於長度3的數列 不可能會有 長度3以上的子等差數列. 直接回傳 0
line 8: 取一個名為delta的變數 放入等差, 之後可以用delta判斷當前的數列是不是等差數列
line 10 -12: 用找到的特徵來計算子數列數
line 14 -15: 考慮到 [1,2,3,4,6,7,8] 這種例子, 中間斷了5, 所以delta跟count 重新算



這題想了很久 最後感謝高手的文章 才有idea, 原文來自:

 http://bookshadow.com/weblog/2016/10/09/leetcode-arithmetic-slices/