leetcode 力扣 1087 最长等差数列 题解 算法题
发布时间：2022-11-22 10:01:58
题目:最长等差数列
给你一个整数数组nums，返回nums中最长等差子序列的长度。
回想一下，nums的子序列是一个列表nums[i1],nums[i2],...,nums[ik]，且0<=i1。并且如果seq[i+1]-seq[i](0<=i的值都相同，那么序列seq是等差的。示例1：
输入：nums=[3,6,9,12]输出：4解释：
整个数组是公差为3的等差数列。
示例2：
输入：nums=[9,4,7,2,10]输出：3解释：
最长的等差子序列是[4,7,10]。
示例3：
输入：nums=[20,1,15,3,10,5,8]输出：4解释：
最长的等差子序列是[20,15,10,5]。
提示：••
2<=nums.length<=10000<=nums[i]<=500
语言:java
classSolution{
publicintlongestArithSeqLength(int[]nums{
intn=nums.length;
Setdiffs=newHashSet<>(;
for(inti=0;i
for(intj=i+1;j
diffs.add(nums[j]-nums[i];
}
}
intres=2;
for(intdiff:diffs{
res=Math.max(res,LS(nums,diff;
}
returnres;}
publicintLS(int[]arr,intdifference{
Mapmap=newHashMap<>(;
intres=1;
for(inti=0;ilength;i++{
intval=map.getOrDefault(arr[i]-difference,0;
map.put(arr[i],val+1;
res=Math.max(res,val+1;
}
returnres;}}
语言:java
classSolution{ 