题目描述
思路
DP
代码

leetcode daily 446. 等差数列划分 II - 子序列

August 11, 2021

题目描述

给你一个整数数组 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:

输入: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:

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

提示:

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

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

思路

DP

求当前序列 sequence 的等差子序列数量

定义状态 dp[i][j] 为序列 sequence[0…i] 且等差为 d 的子序列长度。则状态转移方程为

for dd in (0, d):
  dp[i+1][j] += dp[sequence[i] - dd][d]

最终的所有子序列数量为所有长度 d 以及的集合

for i in (0, sequence.length)
  for dd in (0, d)
    result[i] += dp[i][dd]

又根据原题,只需要计算序列长度最少为 3 的子序列数量, 只需要 等差子序列数量 total - 等差为 2 的子序列长度 total_2

total_2 = 给定数列的随机两个数的组合数 = length * (length - 1) / 2, length 为给定序列长度

Tips: 由于给定的数列为稀疏序列,因此可以用哈希表来存等差序列的等差值

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfArithmeticSlices = function (nums) {
  let { length: len } = nums;
  const mapArr = Array.from(nums);

  for (let i = 0; i < len; i++) {
    let curMap = new Map();
    for (let j = 0; j < i; j++) {
      let d = nums[i] - nums[j];
      const preMap = mapArr[j];
      let curCount = curMap.get(d) || 0;
      curCount = 1 + curCount + (preMap.get(d) || 0);
      curMap.set(d, curCount);
    }
    mapArr[i] = curMap;
  }

  let total = 0;
  for (let map of mapArr) {
    for (let [k, v] of map) {
      total += v;
    }
  }

  return total - (len * (len - 1)) / 2;
};

console.log(numberOfArithmeticSlices([2, 4, 6, 8, 10]));
  • 时间复杂度: $O(N * N)$, N 为序列长度
  • 空间复杂度: $O(N * N)$, N 为序列长度

feiker 少年起而行之