LeetCode刷题【1218】最长定差子序列

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

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

 

示例 1：

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

示例 2：

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

示例 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

上代码

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] dp = new int[arr.length];
        dp[0]=1;
        map.put(arr[0],1);
        int i = 1;
        for (; i < arr.length; i++) {
            dp[i] = Math.max(dp[i-1], map.getOrDefault(arr[i]-difference,0)+1 );
            map.put(arr[i],map.getOrDefault(arr[i]-difference,0)+1);
        }
        return dp[--i];
    }
}

思路简析

建立对应长度DP数组，第i位置表示最长等差子序列的长度，详细思路的写在注解里

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] dp = new int[arr.length];
        //第一位的时候显然最长一定为1
        dp[0]=1;
        //表示以arr[0]为结尾的等差数列子序列的长度为1
        map.put(arr[0],1);
        int i = 1;
        for (; i < arr.length; i++) {
            //第i位的时候。
            //此时也许当前值减去difference的值，在map中有记录存在有这个值结尾的等差数列，
            //也可能这个等差数列的长度比之前[i-1]位的等差数列的长度要小，
            //俩着取较大的一个
            dp[i] = Math.max(dp[i-1], map.getOrDefault(arr[i]-difference,0)+1 );
            //在map中记录或者更新更新以当前值结尾的等差数列子序列的最大长度
            map.put(arr[i],map.getOrDefault(arr[i]-difference,0)+1);
        }
        return dp[--i];
    }
}

换个角度

上面的写法中使用HashMap的原因是key值可能为负数，如果是正数int型的key的话一般还有一种做法是直接用int[]数组代替hashmap来处理相关逻辑，比封装后的HashMap更加简洁高效，当时相对的也有更多局限性。

本题中给出了-10⁴ <= arr[i], difference <= 10⁴

那么arr[i]的范围就在-9999到9999之间，如果再加上需要和difference运算的话，那么应该是-20000 < arr[i] +/- difference < 20000 之间，那么对应的上面的int[]数组代替hashmap的更加高效的选择的作法的话，就变成如下的代码

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        int[] map = new int[40001];
        int[] dp = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr[i]+20000;
        }
        dp[0]=1;
        map[arr[0]] = 1;
        int i = 1;
        for (; i < arr.length; i++) {
            dp[i] = Math.max(dp[i-1], map[arr[i]-difference]+1 );
            map[arr[i]]= map[arr[i]-difference]+1;
        }
        return dp[--i];
    }
}