446_javascript.js

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

/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfArithmeticSlices = function (nums) {
  let length = nums.length;
  if (length < 3) return 0;
  // dp[i][j] 为以nums[i]为结尾 公差为j的子序列数目
  let dp = {};
  let res = 0;
  for (let index in nums) {
    dp[index] = {};
  }

  for (let i = 0; i < length; i++) {
    for (let j = 0; j < i; j++) {
      let diff = nums[i] - nums[j];
      // 计算 从diff[0][diff] 到 diff[i][diff] 的值
      // 即 计算公差为diff的序列数目
      let current = dp[j][diff] || 0;
      // res 取值此处 将dp[i][diff] 之前的值全部相加
      // 如何判断是至少三个数的等差数列
      // 如果当前 获取 diff  差值为 相同的 dp[j][diff]
      // 只要之前的diff 和当前diff 相同 那么就可以加上 dp[j][diff]
      // 如 2 4 6 8 10
      // dp[1][2] = 1 到4这个值的时候公差为2 那么 有一个 子数组 [2,4]
      // dp[2][2] = 2 到6 有 说明可以接在 查找前面项 dp[1][2] 可以接在后面 差值一样[2,4,6] 新增一个等差数列 需+1
      // ...
      res += current;
      dp[i][diff] = (dp[i][diff] || 0) + current + 1;
    }
  }
  // 最后循环dp的最后一个元素获取其公差总数
  return res;
};

// 2 4 6        1
// 2 4 6 8      3
// 2 4 6 8 10   7

// 2   4   6    8    10
// 以上为例 得出的dp数组
// {
//   0: {},
//   1: {
//     2: 1,
//   },
//   2: {
//     2: 2,
//     4: 1,
//   },
//   3: {
//     2: 3,
//     4: 1,
//     6: 1,
//   },
//   4: {
//     2: 4,
//     4: 2,
//     6: 1,
//     8: 1,
//   },
// };