等差数列划分 II - 子序列

Category Difficulty Likes Dislikes
algorithms Hard (54.91%) 262 -
Tags

Companies

给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。

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

  • 例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
  • 再例如，[1, 1, 2, 5, 7] 不是等差序列。

数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。

  • 例如，[2,5,10] 是 [1,2,1,***2***,4,1,***5\***,***10***] 的一个子序列。

题目数据保证答案是一个 32-bit 整数。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：nums = [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]

示例 2：

1
2
3
输入：nums = [7,7,7,7,7]
输出：16
解释：数组中的任意子序列都是等差子序列。

提示：

  • 1 <= nums.length <= 1000
  • -231 <= nums[i] <= 231 - 1

动态规划+哈希表(c++)

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem446.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=446 lang=cpp
 *
 * [446] 等差数列划分 II - 子序列
 */

/** 
 * f[i][j] = f[k][j] + 1;
 */

// @lc code=start
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        vector<unordered_map<long long, int>> f(n); 
        int res = 0;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                long long k = 1LL * nums[i] - nums[j];
                auto it = f[j].find(k);
                int cnt = it == f[j].end() ? 0 : it->second;
                res += cnt; 
                f[i][k] += cnt + 1;
            }
        }
        return res;
    }
};
// @lc code=end