526互联

[LeetCode] 1218. Longest Arithmetic Subsequence of Given Difference

发布时间 2023-07-15 06:56:05作者: CNoodle

Given an integer array arr and an integer difference, return the length of the longest subsequence in arr which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference.

A subsequence is a sequence that can be derived from arr by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: arr = [1,2,3,4], difference = 1
Output: 4
Explanation: The longest arithmetic subsequence is [1,2,3,4].

Example 2:

Input: arr = [1,3,5,7], difference = 1
Output: 1
Explanation: The longest arithmetic subsequence is any single element.

Example 3:

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

Constraints:

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

最长定差子序列。

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是动态规划。这里我们创建一个dp数组，dp[i] 的定义是记录以数字 nums[i] 结尾的最长等差子序列的长度，同时我们需要一个哈希表存储以数字 nums[i] 结尾的最长等差子序列的长度。然后我们开始扫描 input 数组，对于当前数字 nums[i]，如果数组中存在 nums[i] - difference（看哈希表里是否存在），那么以当前数字结尾的等差子序列的长度 = 以 nums[i] - difference 结尾的等差子序列的长度 + 1。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int longestSubsequence(int[] arr, int difference) {
 3         int res = 0;
 4         HashMap<Integer, Integer> map = new HashMap<>();
 5         for (int num : arr) {
 6             map.put(num, map.getOrDefault(num - difference, 0) + 1);
 7             res = Math.max(res, map.get(num));
 8         }
 9         return res;
10     }
11 }

 

LeetCode 题目总结