1218. 最长定差子序列-北京尧图网络

题目描述给你一个整数数组arrarrarr和一个整数differencedifferencedifference请你找出并返回arrarrarr中最长等差子序列的长度该子序列中相邻元素之间的差等于differencedifferencedifference。子序列是指在不改变其余元素顺序的情况下通过删除一些元素或不删除任何元素而从arrarrarr派生出来的序列。示例 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]。算法原理子序列问题可用动态规划解决状态表示dp[i]dp[i]dp[i]表示以iii为结尾的所有等差子序列中最长等差子序列的长度状态转移方程由于题目给定了差值differencedifferencedifference所以在知道arr[i]aarr[i] aarr[i]a的情况下可以推出它前面的那个值等于a−differenceba - difference ba−differenceb。因此当获得值aaa时就去arrarrarr的[0,i−1][0, i-1][0,i−1]区间中找一个值bbb根据bbb的情况有两种状态[0,i−1][0, i-1][0,i−1]区间中不存在bbb此时aaa自己为一个等差子序列dp[i]1dp[i] 1dp[i]1[0,i−1][0, i-1][0,i−1]区间中存在bbb此时aaa要跟在以bbb为结尾的等差子序列之后假设0ji−10 j i-10ji−1以bbb为结尾的等差子序列它的长度为dp[j]dp[j]dp[j]以aaa为结尾的等差子序列它的长度就是dp[j]1dp[j] 1dp[j]1但是如果这样做就要去遍历[0,i−1][0, i-1][0,i−1]区间了效率太低我们进行优化由于差值固定为differencedifferencedifference当得到arr[i]aarr[i] aarr[i]a时在[0,i−1][0, i-1][0,i−1]区间内找任意一个bbb均可得到以aaa为结尾的最长等差子序列长度所以使用一个哈希表hashhashhash保存某等差子序列最后一个值和该等差子序列长度的映射关系当得到aaa时在hashhashhash中查找bbbbbb不存在就保存hash[a]1hash[a] 1hash[a]1。bbb存在就保存hash[a]hash[b]1hash[a] hash[b] 1hash[a]hash[b]1并更新结果初始化刚开始哈希表什么都没有i0i 0i0时会得到aarr[0]a arr[0]aarr[0]在哈希表中查找[0,−1][0, -1][0,−1]区间上的值bbb肯定是找不到的此时会填入arr[0]0arr[0] 0arr[0]0所以哈希表不需要初始化填表顺序从左到右遍历arrarrarr填充哈希表返回值哈希表中的最大值代码classSolution{public:intlongestSubsequence(vectorintarr,intdifference){unordered_mapint,inthash;// 某等差子序列最后一个值 - 该等差子序列的长度intans1;for(inti0;iarr.size();i){intaarr[i];intba-difference;if(hash.find(b)!hash.end())// 之前有以 b 为结尾的子序列{intlenhash[b];hash[a]len1;// 在以 b 为结尾的子序列之后带上 aansmax(ans,len1);}else// 之前没有以 b 为结尾的子序列{hash[a]1;}}returnans;}};

1218. 最长定差子序列

相关推荐

金融风控场景下Qwen-7B大模型微调实战指南

视频本地化混合翻译方案：AI与人工的黄金比例

如何为Nodejs后端服务配置Taotoken统一大模型调用接口

更多资讯

libpqxx 7.7.3 configure 脚本构建指南：从编译、测试到安装的完整实战（ZeroTierOne 仓库内置源码）

Wagtail 无障碍实践全指南：从内容建模到自定义 Axe 内容检查器

Java小白看过来！掌握Spring AI，抢占AI求职入场券

wgpu 在 Android 与 iOS 上运行测试：交叉编译配置与 adb/ssh 设备端执行完整指南

独立站数据漏报是怎么发生的？五个常见断点

marimo 函数复用机制详解：用 setup cell 与 @app.function 将笔记本中的函数与类导出为可导入模块

今日更新

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？