4-22每日

1027. 最长等差数列

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

示例 1：

输入：nums = [3,6,9,12]
输出：4
解释： 
整个数组是公差为 3 的等差数列。

题解：dp

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestArithSeqLength = function(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(0).map(() => new Map()); // 初始化 dp 数组，每个位置对应一个哈希表，用于存储以该位置为结尾、以其差值为公差的等差数列的长度

    let res = 2; // 初始化结果为 2，因为任意两个数都是等差数列

    for (let j = 1; j < n; j++) &#123; // 枚举等差数列的最后一项
        for (let i = 0; i < j; i++) &#123; // 枚举等差数列的倒数第二项
            const d = nums[j] - nums[i]; // 计算等差数列的差值

            if (dp[i].has(d)) &#123; // 如果 dp[i] 中存在该差值
                dp[j].set(d, dp[i].get(d) + 1); // 转移，更新以 nums[j] 结尾、以差值 d 为公差的等差数列的长度为 dp[i].get(d) + 1
            &#125; else &#123; // 如果 dp[i] 中不存在该差值
                dp[j].set(d, 2); // 初始化以 nums[j], nums[i] 为首尾、以差值 d 为公差的等差数列的长度为 2
            &#125;

            res = Math.max(res, dp[j].get(d)); // 更新全局最长等差子序列的长度 res
        &#125;
    &#125;

    return res; // 返回最长等差数列的长度
&#125;;