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
即等差數(shù)列。
問題：
找出數(shù)組A中等差數(shù)列的個數(shù)转晰，A不一定是等差數(shù)列。
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.
思路:
- 長度為n的數(shù)組A為等差數(shù)列支示，在數(shù)組后面增加一個數(shù)，若數(shù)組最后一個數(shù)的兩倍等于數(shù)組倒數(shù)第二個數(shù)加新數(shù)鄙才，則新數(shù)與數(shù)組A組成一個新的等差數(shù)列颂鸿。
- 長度為n的數(shù)組A不是等差數(shù)列，則在數(shù)組面增加新數(shù)組成的新數(shù)組不可能是等差數(shù)列
Solution
class Solution:
def numberOfArithmeticSlices(self, A):
"""
:type A: List[int]
:rtype: int
"""
n = len(A)
count = 0
available = list(range(1, n))
while True:
new_available = []
for i in available:
if i < n - 1 and A[i + 1] + A[i - 1] == 2 * A[i]:
new_available.append(i+1)
count += 1
available = new_available
if len(available) == 0:
break
return count
