LeetCode 5214. 最长定差子序列(Java)HashMap
2024-10-21 06:22:07
题目: 5214. 最长定差子序列
给你一个整数数组 arr
和一个整数 difference
,请你找出 arr
中所有相邻元素之间的差等于给定 difference
的等差子序列,并返回其中最长的等差子序列的长度。
示例 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 <= 10^5
-10^4 <= arr[i], difference <= 10^4
题解:
Map<key, value>
保存以 key
结束的序列的最大长度。
遍历数组 arr
,数 k
的前驱结点为 pre = k - difference
,因此以 k
结束的序列的长度加 1,更新最大值(返回值),并更新 map
中 key = k
时的 value
。
时间复杂度: O(n)O(n)O(n),不考虑 HashMap
中查找的时间复杂度
空间复杂度: 不确定
Java:
class Solution {
public int longestSubsequence( int[] arr,
int difference) {
Map<Integer, Integer> map = new HashMap<>();
int ret = 0;
for (int k : arr) {
int pre = k - difference;// 前驱
// 序列增加数k,因此长度加1
int len = map.getOrDefault(pre, 0) + 1;
ret = Math.max(ret, len);
map.put(k, len);// 更新map
}
return ret;
}
}
最新文章
- Python成长笔记 - 基础篇 (十三)--堡垒机
- Oracle笔记 十三、PL/SQL面向对象之package
- LINUX下成功搭建SVN
- java.sql.SQLException: Before start of result set解决方法
- Seek the Name, Seek the Fame - POJ 2752(next运用)
- Java -- WeakHashMap
- java中完美打包
- Day2 python基础学习
- 图解ARP协议(三)ARP防御篇-如何揪出“内鬼”并“优雅的还手”
- LeetCode算法题-Count Binary Substrings(Java实现)
- springMVC的配置与使用
- HTML5 浏览器支持
- python基础(五)
- Tmux 常用快捷键
- 包建强的培训课程(1):Android App企业级开发
- 前端框架之Vue(5)-条件渲染
- 机器学习算法与Python实践之(六)二分k均值聚类
- 【转】Scheme 编程环境的设置
- 用Entityframework 调用Mysql时,datetime格式插入不进去数据库的解决办法。
- python安装HTMLTestRunner