1027.最长等差数列

【LetMeFly】1027.最长等差数列

力扣题目链接：https://leetcode.cn/problems/longest-arithmetic-subsequence/

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。

回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 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 <= 1000
• 0 <= nums[i] <= 500

方法一：枚举公差（哈希表）

首先预处理遍历一遍数组，找到数组中的最大值和最小值，最大值和最小值之差记为$diff$。那么，等差数列的公差一定在$[-diff, diff]$之间。

枚举每一个可能的$diff$。当公差枚举到$d$时：

使用一个哈希表$ma$，其中$ma[n]$代表公差为$d$时，以$n$结尾的等差数组的现有长度。

这样，我们只需要遍历原始数组，当我们遍历到$n$时，如果$n-d$已经在哈希表中，那么$n$就可以添加到$n-d$结尾的哈希表的末尾（长度为原有长度加一）；反之，$n$必须自己打头开始作为一个等差数列的首项（长度为1）

• 时间复杂度$O(len(nums)\times (\max(nums)+\min(nums)))$（时间复杂度中max(nums)-min(nums)的复杂度取决于二者较大的一个）
• 空间复杂度$O(len(nums))$

AC代码

C++

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int ans = 2;
        auto minmax = minmax_element(nums.begin(), nums.end());
        int diff = *minmax.second - *minmax.first;
        for (int d = -diff; d <= diff; d++) {  // 要从-diff开始
            unordered_map<int, int> ma;
            for (int num : nums) {
                int thisAns;  // 其实可以直接 int thisAns = ma[num - d] + 1
                if (ma.count(num - d)) {
                    thisAns = ma[num - d] + 1;
                }
                else {
                    thisAns = 1;
                }
                ma[num] = thisAns;
                ans = max(ans, thisAns);
            }
        }
        return ans;
    }
};

Python

# from typing import List

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        ans = 2
        diff = max(nums) - min(nums)
        for d in range(-diff, diff + 1):
            mp = dict()
            for num in nums:
                if num - d in mp:
                    thisAns = mp[num - d] + 1
                else:
                    thisAns = 1
                mp[num] = thisAns
                ans = max(ans, thisAns)
        return ans

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/130301122