leetcode 446 等差数列划分 II - 子序列
z
 2019-06-28 17:17:17  

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。例如，以下数列为等差数列:

1
2
3
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

以下数列不是等差数列。

1
1, 1, 2, 5, 7

数组 A 包含 N 个数，且索引从 0 开始。该数组子序列将划分为整数序列 $(P_0, P_1, …, P_k)$，P 与 Q 是整数且满足 $0 ≤ P_0 < P_1 < … < P_k < N$。

如果序列 $A[P_0]，A[P_1]，…，A[P_{k-1}]，A[P_k]$ 是等差的，那么数组 A 的子序列$ (P_0，P_1，…，P_K)$ 称为等差序列。值得注意的是，这意味着 k ≥ 2。

函数要返回数组 A 中所有等差子序列的个数。

输入包含 N 个整数。每个整数都在 $-2^{31}$ 和 $2^{31-1}$ 之间，另外 0 ≤ N ≤ 1000。保证输出小于 $2^{31-1}$。

示例：

1
2
3
4
5
6
7
8
9
10
11
输入：	[2, 4, 6, 8, 10]
输出：	7
解释：
      所有的等差子序列为：
      [2,4,6]
      [4,6,8]
      [6,8,10]
      [2,4,6,8]
      [4,6,8,10]
      [2,4,6,8,10]
      [2,6,10]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        distList = [dict() for i in range(len(A))]
        ans = 0
        for i in range(1, len(A)):
            for j in range(i):
                delta = A[i] - A[j]
                if delta not in distList[i]:
                    distList[i][delta] = 0
                distList[i][delta] += 1
                if delta in distList[j]:
                    distList[i][delta] += distList[j][delta]
                    ans += distList[j][delta]
        return ans