线性动态规划：统计只出现一次的最长连续子序列的长度 题目描述 给定一个整数数组nums，我们需要找到最长的连续子序列的长度，要求这个子序列中每个元素都只出现一次。换句话说，在找到的连续子数组里，不能有重复的数字。 例如： 输入：nums = [ 1, 2, 3, 2, 1 ] 输出：3 解释：最长的满足条件的连续子序列是 [ 1, 2, 3] 或者 [ 2, 3, 2] 是不合法的，因为数字2重复了。实际上，最长的是 [ 1, 2, 3] 或 [ 3, 2, 1 ]，长度都是3。 解题过程 这个问题可以通过滑动窗口（Sliding Window）技术高效解决，其本质也是一种线性动态规划思想。我们将维护一个窗口，并通过一个哈希表（或称为字典）来记录窗口内每个数字最近一次出现的位置。 定义状态 我们使用两个指针 left 和 right 来表示当前窗口的左右边界。窗口是子数组 nums[left...right] 。我们的目标是找到最大的 (right - left + 1) ，使得窗口内所有数字都是唯一的。 我们还需要一个哈希表 last_occurrence ，其键（key）是数字，值（value）是该数字 最近一次 出现时的索引位置。 状态转移（窗口滑动） 初始化 left = 0 ， max_length = 0 。 让 right 指针从 0 遍历到 len(nums) - 1 。 对于每个 right ，我们检查当前数字 nums[right] ： 如果 nums[right] 从未出现过，或者它上次出现的位置 last_occurrence[nums[right]] 在当前窗口起始位置 left 的 左边 （即 last_occurrence[nums[right]] < left ），说明当前数字在当前窗口内是唯一的。我们可以安全地将它纳入窗口。 否则，如果 nums[right] 上次出现的位置 last_occurrence[nums[right]] 位于当前窗口内（即 >= left ），说明我们遇到了一个重复数字。这时，我们必须移动左指针 left 。为了确保新窗口内没有重复，我们将 left 移动到 last_occurrence[nums[right]] + 1 。这个操作将那个重复的数字（上一次出现的那次）移出了窗口。 在每次移动 right 指针后，无论是否更新了 left ，我们都更新 nums[right] 在 last_occurrence 中的值为当前的索引 right 。 同时，计算当前窗口的长度 current_length = right - left + 1 ，并更新 max_length = max(max_length, current_length) 。 算法步骤详解（以 nums = [ 1, 2, 3, 2, 1] 为例） 初始化: left = 0 , max_length = 0 , last_occurrence = {} right = 0: num = 1。1 不在 last_ occurrence 中。窗口 [ 1]，长度=1。last_ occurrence[ 1]=0。max_ length=1。 right = 1: num = 2。2 不在 last_ occurrence 中。窗口 [ 1,2]，长度=2。last_ occurrence[ 2]=1。max_ length=2。 right = 2: num = 3。3 不在 last_ occurrence 中。窗口 [ 1,2,3]，长度=3。last_ occurrence[ 3]=2。max_ length=3。 right = 3: num = 2。2 在 last_ occurrence 中，且上次出现在索引1 ( last_occurrence[2]=1 )， 1 >= left(0) ，说明2在窗口内重复了。将 left 移动到 1 + 1 = 2 。新窗口为 [ 3,2] (索引2和3)。更新 last_occurrence[2]=3 。当前长度=2。max_ length 保持3。 right = 4: num = 1。1 在 last_ occurrence 中，上次出现在索引0 ( last_occurrence[1]=0 )， 0 < left(2) ，说明这个1不在当前窗口内，可以加入。窗口变为 [ 3,2,1] (索引2,3,4)。更新 last_occurrence[1]=4 。当前长度=3。max_ length=3。 遍历结束，最终结果 max_ length = 3。 复杂度分析 时间复杂度：O(n)，其中 n 是数组长度。我们只遍历了数组一次。 空间复杂度：O(min(n, m))，其中 m 是数组中不同数字的个数。哈希表最多存储 m 个键值对。 这个算法巧妙地利用了哈希表记录位置和滑动窗口的思想，避免了暴力枚举所有子数组，从而在线性时间内解决了问题。