LeetCode 446: Arithmetic Slices II - Subsequence

发表于 | | 阅读次数:
字数统计: 778 | 阅读时长 ≈ 3

题目链接

https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence/

题意

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

例如，以下数列为等差数列:

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

以下数列不是等差数列。

1, 1, 2, 5, 7

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

如果序列 A[P0]，A[P1]，…，A[Pk-1]，A[Pk] 是等差的，那么数组 A 的子序列 (P0，P1，…，PK) 称为等差序列。值得注意的是，这意味着 k ≥ 2。

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

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

示例：

输入：[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] Arithmetic Slices II - Subsequence 算数切片之二 - 子序列解出。
dp[i][diff] dp的数组分为两维:
第一维表示以第i个数字作为结尾，第二维表示公差为diff，
其值表示以i为结尾的公差为diff的等差数列的个数
枚举j < i, 置diff = A[i] - A[j]:

  1. 考虑等差数列只有i, j两个数的情况, ++dp[i][diff]
  2. 在j结尾的公差为diff的各数列后加上一个A[i]构成新数列, 即dp[i][diff] += dp[j][diff]
  3. 2中构成的新数列个数必然>2且以A[i]结尾(防止统计重合),正好res += dp[j][diff];

由于整数数目太大使用unordered_map<int, int>节省时间空间。
本题LeetCode上C++不知为何通不过(应该和常数时间有关系)，最后用了几乎一样的Python通过的。

时间复杂度

$O(N ^ 2)$

源代码CPP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
typedef long long ll;
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int n = A.size();
        int i, j, res = 0;
        if (n == 0)
            return 0;
        vector<unordered_map<int, int> >dp(n);
        for (i = 1; i < n; i++) {
            for (j = 0; j < i; j++) {
                ll delta = (ll)A[i] - A[j];
                if (delta > INT_MAX || delta < INT_MIN)
                    continue;
                int diff = (int)delta;
                ++dp[i][diff];
                if (dp[j].count(diff)) {
                    dp[i][diff] += dp[j][diff];
                    res += dp[j][diff];
                }
            }
        }
        return res;
    }
};

源代码Python

Python代码来自Ziqiang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        total = 0
        dp = [collections.defaultdict(int) for item in A]
        for i in xrange(len(A)):
            for j in xrange(i):
                dp[i][A[i] - A[j]] += 1 #dp[i][j]表示在index i这个点，间隔为j的序列的数量
                if A[i]-A[j] in dp[j]: #j<i
                    dp[i][A[i] - A[j]] += dp[j][A[i]-A[j]] #为什么上面加的那一次不重复？
                    total += dp[j][A[i]-A[j]] #因为每次update total是根据j，不是根据i，下次才根据i
        return total
0%