26. Longest Arithmetic Subsequence with Given Difference

Origin: Longest Arithmetic Subsequence with Given Difference

Given an array of integers and a positive integer k, find the length of the longest arithmetic progression with common difference k. Ignore duplicates.

Example

Input: arr = [8, 1, -1, 0, 3, 6, 2, 4, 5, 7, 9], k = 2

Output: 6

Explanation: 去重后找公差为 2 的最长等差数列。从 -1 开始：[-1, 1, 3, 5, 7, 9]，长度 6。

Input Format

• 第一行：n（数组长度）
• 接下来 n 行：每行一个数组元素
• 最后一行：k（公差）

Constraints

• 0 <= arr.length <= 100000
• -10^9 <= arr[i] <= 10
• 1 <= k <= 10
• 数组可能有重复值，形成等差数列时忽略重复

Output Format

返回一个整数：最长等差数列的长度。

Sample Input 0

0
5

Sample Output 0

0

Sample Input 1

1
42
7

Sample Output 1

1

---

函数契约

// 输入：arr（整数数组），k（公差，正整数）
// 输出：最长等差数列的长度（整数）
// 边界：空数组 → 0；单元素 → 1；无等差数列 → 1（单个元素也算长度 1）

边界表

场景	返回什么
空数组	0
单元素	1
所有元素都不构成等差数列	1
正常场景	最长等差数列长度

Resolution

我的解法

function findLongestArithmeticProgression(arr: number[], k: number): number {
    const deduplicatedArr = Array.from(new Set(arr)).sort((a, b) => a - b);
    const dpMap = new Map<number, number>();
    let maxLength = 0;
    for (const x of deduplicatedArr) {
        const pre = x - k;
        if (dpMap.has(pre)) {
            dpMap.set(x, dpMap.get(pre)! + 1);
        } else {
            dpMap.set(x, 1);
        }
        maxLength = Math.max(maxLength, dpMap.get(x)!);
    }
    return maxLength;
}

解题思路

这道题是 DP + 哈希表的组合。

四步推导：

1. 定义状态：dp[x] = 以 x 结尾的等差数列长度
2. 前一步是什么：x 的前一个数是 x-k。如果 x-k 在数组里，dp[x] = dp[x-k] + 1；否则 dp[x] = 1
3. 边界：第一个出现的数 dp[x] = 1，空数组返回 0
4. 方向：排序后从小到大遍历，保证 x-k 在 x 之前被处理

为什么必须排序？ 不排序时按原始顺序遍历，1 在 -1 前面出现，dp[1] 算的时候 dp[-1] 还没存进 Map，dp[1] 被设为 1 而不是 2，后面全部差 1。排序后 x-k 一定比 x 小，一定先被处理过，dp[x-k] 已经算好了。

为什么用哈希表不用数组？ arr[i] 范围 ±10^9，数组下标存不下，用 Map 代替。

为什么是 DP？ 不是因为有”选择”，而是因为暴力解有重复计算。算 9 的链要经过 7→5→3→1→-1，算 7 的链也要经过 5→3→1→-1，5→3→1→-1 被算了两遍。DP 把中间结果存起来只算一遍。识别 DP 的真正信号是”有没有重复计算”，不是”有没有选择”。

暴力解法（超时，4 个用例不过）

function findLongestArithmeticProgression(arr: number[], k: number): number {
    const set = new Set(arr)
    const deduplicatedArr = Array.from(new Set(arr));
    let maxLength = 0;
    for (let i = 0; i < deduplicatedArr.length; i++) {
        let cur = deduplicatedArr[i];
        let flag = true
        let length = 1;
        while (flag) {
            let next = cur + k
            if (set.has(next)) {
                length++;
                cur = next;
            } else {
                flag = false;
            }
        }
        maxLength = Math.max(maxLength, length);
    }
    return maxLength;
}

暴力解用 Set 做 O(1) 查询，从每个元素往后找 x+k、x+2k…… 找不到就停。最坏情况 O(n²)（所有元素连成一条链），n=100000 时超时。

两解对比

	暴力解	DP 解
思路	每个元素往后找整条链	查一次 dp[x-k] 拿到链长度
时间	O(n × L)，L 是最长链长度，最坏 O(n²)	O(n log n)，排序是主要开销
空间	O(n)，Set	O(n)，Map
需要	不排序	必须排序

复杂度

• 时间：O(n log n)，排序是主要开销
• 空间：O(n)，Map 存 dp 值

参考来源

• 相关题型：动态规划
• 相关文章：算法解题流程：从读题到提交的七步