线性动态规划：统计只出现一次的最长连续子序列的长度

字数 1522 2025-11-28 14:49:29

线性动态规划：统计只出现一次的最长连续子序列的长度

题目描述
给定一个整数数组 nums，你需要找到最长的连续子序列，使得这个子序列中每个元素恰好只出现一次。返回这个最长子序列的长度。

例如：
输入：nums = [1, 2, 3, 2, 1, 4, 5]
输出：5
解释：最长符合条件的子序列是 [1, 4, 5, 2, 3] 或 [3, 2, 1, 4, 5]，但注意题目要求是连续子序列（即原数组中的连续一段），所以实际应从原数组选取连续区间。在示例中，最长有效连续子序列是 [2, 3, 2, 1, 4, 5] 中剔除重复元素后的连续段？这里需要澄清：题目要求连续子序列内无重复元素。实际上，[1, 2, 3] 长度为 3，[2, 3, 2] 无效（2重复），[3, 2, 1, 4, 5] 长度为 5（索引 2 到 6）。所以输出 5。

解题思路
此题是典型的滑动窗口配合动态规划思想的线性 DP 问题。我们可以用双指针维护一个窗口，保证窗口内无重复元素，同时用哈希表记录每个元素最近一次出现的索引。当右指针遇到重复元素时，左指针需要移动到重复元素上次出现位置的下一个位置。

详细步骤

定义变量
- left：当前无重复子数组的左边界（初始为 0）。
- maxLen：记录最长无重复子数组的长度（初始为 0）。
- lastIndex：哈希表（或字典），记录每个元素最近一次出现的索引。
遍历数组
用右指针 right 从 0 到 n-1 遍历数组：
- 若当前元素 nums[right] 已在 lastIndex 中，且其上次出现的索引 ≥ left，说明当前窗口内出现了重复。
- 更新 left = lastIndex[nums[right]] + 1，将窗口左边界移动到重复元素之后。
- 更新 lastIndex[nums[right]] = right，记录当前元素的最新索引。
- 计算当前窗口长度 right - left + 1，并更新 maxLen。
动态规划思想
虽然此题常用滑动窗口，但可以理解为一种线性 DP：
- 定义 dp[i] 为以 i 结尾的最长无重复子数组的长度。
- 状态转移：
```
dp[i] = min(dp[i-1] + 1, i - lastIndex[nums[i]])
```
  即：当前长度要么是上一个位置长度加 1，要么是从上次出现位置之后到当前位置的长度。
- 最终结果为 max(dp[0..n-1])。
举例说明
以 nums = [1, 2, 3, 2, 1, 4, 5] 为例：
- right=0：元素 1，lastIndex={1:0}，窗口 [0:0]，长度=1。
- right=1：元素 2，lastIndex={1:0, 2:1}，窗口 [0:1]，长度=2。
- right=2：元素 3，lastIndex={1:0, 2:1, 3:2}，窗口 [0:2]，长度=3。
- right=3：元素 2（重复，上次索引=1 ≥ left=0），左移 left=2，窗口 [2:3]，长度=2。
- right=4：元素 1（重复，上次索引=0 < left=2？不调整？不对，检查：当前 left=2，元素 1 上次索引 0 < 2，所以不移动 left，但需更新 lastIndex[1]=4。窗口 [2:4]，长度=3。
- 继续直至结束，最大长度在 [2:6] 即 [3,2,1,4,5] 长度为 5。
复杂度分析
- 时间复杂度：O(n)，每个元素被访问一次。
- 空间复杂度：O(m)，m 为不同元素个数。

通过以上步骤，即可高效求出最长无重复元素的连续子序列长度。

线性动态规划：统计只出现一次的最长连续子序列的长度题目描述给定一个整数数组 nums ，你需要找到最长的连续子序列，使得这个子序列中每个元素恰好只出现一次。返回这个最长子序列的长度。例如：输入： nums = [1, 2, 3, 2, 1, 4, 5] 输出： 5 解释：最长符合条件的子序列是 [1, 4, 5, 2, 3] 或 [3, 2, 1, 4, 5] ，但注意题目要求是连续子序列（即原数组中的连续一段），所以实际应从原数组选取连续区间。在示例中，最长有效连续子序列是 [2, 3, 2, 1, 4, 5] 中剔除重复元素后的连续段？这里需要澄清：题目要求连续子序列内无重复元素。实际上， [1, 2, 3] 长度为 3， [2, 3, 2] 无效（2重复）， [3, 2, 1, 4, 5] 长度为 5（索引 2 到 6）。所以输出 5。解题思路此题是典型的滑动窗口配合动态规划思想的线性 DP 问题。我们可以用双指针维护一个窗口，保证窗口内无重复元素，同时用哈希表记录每个元素最近一次出现的索引。当右指针遇到重复元素时，左指针需要移动到重复元素上次出现位置的下一个位置。详细步骤定义变量 left ：当前无重复子数组的左边界（初始为 0）。 maxLen ：记录最长无重复子数组的长度（初始为 0）。 lastIndex ：哈希表（或字典），记录每个元素最近一次出现的索引。遍历数组用右指针 right 从 0 到 n-1 遍历数组：若当前元素 nums[right] 已在 lastIndex 中，且其上次出现的索引 ≥ left ，说明当前窗口内出现了重复。更新 left = lastIndex[nums[right]] + 1 ，将窗口左边界移动到重复元素之后。更新 lastIndex[nums[right]] = right ，记录当前元素的最新索引。计算当前窗口长度 right - left + 1 ，并更新 maxLen 。动态规划思想虽然此题常用滑动窗口，但可以理解为一种线性 DP：定义 dp[i] 为以 i 结尾的最长无重复子数组的长度。状态转移：即：当前长度要么是上一个位置长度加 1，要么是从上次出现位置之后到当前位置的长度。最终结果为 max(dp[0..n-1]) 。举例说明以 nums = [1, 2, 3, 2, 1, 4, 5] 为例： right=0 ：元素 1，lastIndex={1:0}，窗口 [ 0:0 ]，长度=1。 right=1 ：元素 2，lastIndex={1:0, 2:1}，窗口 [ 0:1 ]，长度=2。 right=2 ：元素 3，lastIndex={1:0, 2:1, 3:2}，窗口 [ 0:2 ]，长度=3。 right=3 ：元素 2（重复，上次索引=1 ≥ left=0），左移 left=2，窗口 [ 2:3 ]，长度=2。 right=4 ：元素 1（重复，上次索引=0 < left=2？不调整？不对，检查：当前 left=2，元素 1 上次索引 0 < 2，所以不移动 left，但需更新 lastIndex[ 1]=4。窗口 [ 2:4 ]，长度=3。继续直至结束，最大长度在 [2:6] 即 [3,2,1,4,5] 长度为 5。复杂度分析时间复杂度：O(n)，每个元素被访问一次。空间复杂度：O(m)，m 为不同元素个数。通过以上步骤，即可高效求出最长无重复元素的连续子序列长度。