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

链接：446.等差数列划分II-子序列
难度：Hard
标签：数组、动态规划
简介：给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。

题解 1 - typescript

• 编辑时间：2021-08-11
• 执行用时：396ms
• 内存消耗：73.1MB
• 编程语言：typescript
• 解法介绍：动态规划,dp[i]=以 nums[i]结尾的公差映射。

function numberOfArithmeticSlices(nums: number[]): number {
  const map = new Map<number, Map<number, number>>(
    nums.map((_, i) => [i, new Map<number, number>()])
  );
  const n = nums.length;
  let ans = 0;
  for (let i = 0; i < n; i++) {
    const num = nums[i];
    for (let j = 0; j < i; j++) {
      const v = num - nums[j];
      const c = map.get(j)!.get(v) ?? 0;
      ans += c;
      map.get(i)!.set(v, (map.get(i)!.get(v) ?? 0) + c + 1);
    }
  }
  return ans;
}