1218. 最长定差子序列

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。

子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

示例 1：

1
2
3
输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。

示例 2：

1
2
3
输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。

示例 3：

1
2
3
输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是 [7,5,3,1]。

提示：

  • 1 <= arr.length <= 105
  • -104 <= arr[i], difference <= 104

题解：

动态规划

当前数字num所能构成的最长定差子序列的长度由num - difference所能构成的最长定差子序列长度决定。

使用dp[i]来表示以第i个元素为结尾的最长等差子序列的长度，可以通过等差公式:arr[i] - diffience = arr[j]，找到左侧的前一个以arr[j]为结尾的最长定差子序列，将arr[i]加到该子序列中，就可以根据dp[j]递推出dp[i]。

状态转移方程为：

​ dp[i] = dp[i- difference] + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int longestSubsequence(int[] arr, int difference) {
    //初始化结果为1，因为每个数字都可以单独作为一个等差子序列
    int ans = 1;
    //辅助dp哈希表,键为当前元素，值为最长子序列长度
    Map<Integer, Integer> dp = new HashMap<Integer, Integer>();

    //从头遍历数组,遇到一个数 num，判断num - difference在不在数组里面
    // 也就是看看能不能形成以num为结尾的等差数组
    for (int num : arr) {
        //如果dp数组中存在num - difference，就加一存入以当前元素为键的值中,即dp[i] = dp[i - difference ] + 1
        //如果dp数组中不存在num - difference，就初始值为一存入以当前元素为键的值中,即当前元素为一个单独的定差子序列
        int val = dp.getOrDefault(num - difference, 0) + 1;
        //当前位置的最长子序列长度
        dp.put(num, val);
        //记录下来以num结尾的等差数组的长度
        ans = Math.max(ans, val);
    }
    return ans;

}
  • 时间复杂度：O(N)，需要对数组进行遍历。
  • 空间复杂度：O(N)，使用到了元素个数为N的哈希表。