TNotes.leetcode

Appearance

⏰0446. 等差数列划分 II - 子序列【困难】

0446. 等差数列划分 II - 子序列【困难】 ​

1. 📝 题目描述 ​

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

txt
输入：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：

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

提示：

  • 1 <= nums.length <= 1000
  • -2^31 <= nums[i] <= 2^31 - 1

2. 🎯 s.1 - DP + 哈希表 ​

c
#define HASH_SIZE 1009
typedef struct Entry { long long key; int val; struct Entry* next; } Entry;
typedef struct { Entry* buckets[HASH_SIZE]; } HashMap;

HashMap* createMap() {
    HashMap* m = (HashMap*)calloc(1, sizeof(HashMap));
    return m;
}

int getVal(HashMap* m, long long key) {
    int idx = (int)(((unsigned long long)key) % HASH_SIZE);
    for (Entry* e = m->buckets[idx]; e; e = e->next)
        if (e->key == key) return e->val;
    return 0;
}

void addVal(HashMap* m, long long key, int delta) {
    int idx = (int)(((unsigned long long)key) % HASH_SIZE);
    for (Entry* e = m->buckets[idx]; e; e = e->next)
        if (e->key == key) { e->val += delta; return; }
    Entry* e = (Entry*)malloc(sizeof(Entry));
    e->key = key; e->val = delta; e->next = m->buckets[idx]; m->buckets[idx] = e;
}

void freeMap(HashMap* m) {
    for (int i = 0; i < HASH_SIZE; i++) {
        Entry* e = m->buckets[i];
        while (e) { Entry* t = e; e = e->next; free(t); }
    }
    free(m);
}

int numberOfArithmeticSlices(int* nums, int numsSize) {
    int res = 0;
    HashMap** dp = (HashMap**)malloc(sizeof(HashMap*) * numsSize);
    for (int i = 0; i < numsSize; i++) dp[i] = createMap();
    for (int i = 1; i < numsSize; i++) {
        for (int j = 0; j < i; j++) {
            long long d = (long long)nums[i] - nums[j];
            int cnt = getVal(dp[j], d);
            res += cnt;
            addVal(dp[i], d, cnt + 1);
        }
    }
    for (int i = 0; i < numsSize; i++) freeMap(dp[i]);
    free(dp);
    return res;
}
js
/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfArithmeticSlices = function (nums) {
  const n = nums.length
  let res = 0
  // dp[i] 是 Map，key=公差，value=以 nums[i] 结尾的弱等差子序列数（长度>=2）
  const dp = Array.from({ length: n }, () => new Map())
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      const d = nums[i] - nums[j]
      const cnt = dp[j].get(d) || 0
      res += cnt
      dp[i].set(d, (dp[i].get(d) || 0) + cnt + 1)
    }
  }
  return res
}
py
class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [defaultdict(int) for _ in range(n)]
        res = 0
        for i in range(1, n):
            for j in range(i):
                d = nums[i] - nums[j]
                cnt = dp[j][d]
                res += cnt
                dp[i][d] += cnt + 1
        return res
  • 时间复杂度：O(n2)
  • 空间复杂度：O(n2)

算法思路：

  • dp[i][d] 表示以 nums[i] 结尾、公差为 d 的弱等差子序列数（长度 ≥2）
  • 枚举 j < i，计算 d = nums[i] - nums[j]，将 dp[j][d] 累加到结果中（因为加上 nums[i] 后长度 ≥3）