C/C++教程

力扣刷题学习1218. 最长定差子序列(C++)

本文主要是介绍力扣刷题学习1218. 最长定差子序列(C++),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述

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

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

测试用例

示例一:

输入:arr = [1,2,3,4], difference = 1
输出:4
解释:最长的等差子序列是 [1,2,3,4]。

示例 二:

输入:arr = [1,3,5,7], difference = 1
输出:1
解释:最长的等差子序列是任意单个元素。

示例三:

输入:arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出:4
解释:最长的等差子序列是 [7,5,3,1]。

提示:

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

解答

此处用到动态规划的思路,首先从头开始遍历,
对于每个arr中的数,查找arr[i]-d的值存不存在,如果不存在,记录d[arr[i]]=1,若存在则记录d[arr[i]]=d[arr[i]-d]+1;如此遍历循环完整个arr[]数组,随后取max[d[arr[i]]]即为题解。

class Solution {
public:
    int longestSubsequence(vector<int> &arr, int difference) {
        int ans = 0;
        unordered_map<int, int> dp;
        for (int v: arr) {
            dp[v] = dp[v - difference] + 1;
            ans = max(ans, dp[v]);
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度:O(n)O(n),其中 nn 是数组 \textit{arr}arr 的长度。
  • 空间复杂度:O(n)O(n)。哈希表需要 O(n)O(n) 的空间。
这篇关于力扣刷题学习1218. 最长定差子序列(C++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!