📚 力扣每日一题–2025.7.17
📚 3202. 找出有效子序列的最大长度 II（中等）
今天我们要解决的是力扣上的第 3202 题——找出有效子序列的最大长度 II。这道题是昨天 3201 题的扩展，需要我们处理更一般化的情况。
⚠️ 注意：由于使用昨天的方法一直超时且有 bug，今天的内容参考了灵神的思路，前两种完全仿照参考，灵神太牛逼了真的，又简介又高效（原文链接）。
📝 题目描述
给你一个整数数组 nums 和一个 正 整数 k 。
nums 的一个 子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列 ：
(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == … == (sub[x - 2] + sub[x - 1]) % k
返回 nums 的 最长有效子序列 的长度。
一个 子序列 指的是从原数组中删除一些元素（也可以不删除任何元素），剩余元素保持原来顺序组成的新数组。
🤔 思路分析
核心需求推导过程 📝
题目要求子序列中所有相邻元素之和对 k 取模的结果必须相同，即：
(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x-2] + sub[x-1]) % k
令这个共同的模值为 m，则对所有 i 从 0 到 x-2，都有：
(sub[i] + sub[i+1]) % k == m
这个条件比 3201 题中 k=2 的情况更一般化，也更复杂。我们需要分析这个条件背后的数学本质和序列特性。
🧮 数学本质分析
对于等式
(a+b)modk=(b+c)modk
根据 模运算的世界：当加减乘除遇上取模，可以移项，得
(a+b−(b+c))modk=0
化简得
(a−c)modk=0
这意味着 a 与 c 关于模 k 同余。即题目式子中的 sub[i] 与 sub[i+2] 关于模 k 同余。换句话说，有效子序列的偶数项 sub[0],sub[2],sub[4],… 都关于模 k 同余，奇数项 sub[1],sub[3],sub[5],… 都关于模 k 同余。
如果把每个 nums[i] 都改成 nums[i]modk，问题等价于：
求最长子序列的长度，该子序列的奇数项都相同，偶数项都相同。
在模 k 意义下，如果确定了子序列的最后两项，就确定了整个子序列。
🚀 解题方法
方法一：考察子序列的最后两项 🔄
核心思路
这种方法的核心思想是通过观察子序列的最后两项来动态构建有效子序列。我们发现，如果一个有效子序列的最后两项模 k 的结果分别为 y 和 x，那么在它前面添加一个模 k 结果为 y 的元素，就能形成一个新的有效子序列，其最后两项为 x 和 y。
实例解析
以 nums=[1,2,1,2,1,2]，k=3 为例：
- 模 3 后的数组为 [1,2,1,2,1,2]
- 处理第一个元素 1（模 3 后为 1）：
我们可以创建一个以 1 结尾的子序列，此时可以认为它前面有一个虚拟的 2（模 3 后），形成「末尾为 2,1 的子序列」，长度为 1
即 f[2][1] = 1 - 处理第二个元素 2（模 3 后为 2）：
我们可以在「末尾为 1,2 的子序列」后添加 2，但目前不存在这样的子序列
我们也可以在「末尾为 2,1 的子序列」后添加 2，形成「末尾为 1,2 的子序列」，长度为 2
即 f[1][2] = f[2][1] + 1 = 2 - 处理第三个元素 1（模 3 后为 1）：
我们可以在「末尾为 1,2 的子序列」后添加 1，形成「末尾为 2,1 的子序列」，长度为 3
即 f[2][1] = f[1][2] + 1 = 3 - 依此类推，我们不断交替更新 f[1][2] 和 f[2][1]，最终得到 f[1][2] = 6
算法步骤
- 创建一个 k×k 的二维数组 f，f[y][x] 表示最后两项模 k 分别为 y 和 x 的子序列的长度
- 遍历数组中的每个元素 x，计算 x mod k
- 对于每个可能的前一项模 k 值 y（0 到 k-1）：
- 更新 f[y][x] = f[x][y] + 1
- 这表示在以 x 和 y 结尾的子序列后添加当前元素，形成以 y 和 x 结尾的新子序列
- 跟踪 f 中的最大值作为答案
为什么这样可行？
当我们有一个子序列以 (x,y) 结尾，并且我们添加一个新元素 z，使得 (y+z) % k = m（共同的模值），那么新子序列以 (y,z) 结尾。根据前面的数学分析，x ≡ z (mod k)，所以 x 和 z 本质上是相同的模值。这就是为什么我们可以用 f[x][y] + 1 来更新 f[y][x]。
答疑
问：如何理解这个递推？它和记忆化搜索的区别是什么？
答：对比二者的计算顺序。如果用记忆化搜索来做，需要单独计算「最左（或者最右）两项模 k 分别为 x 和 y 的子序列」的长度，这是「单线程」，必须查找下一个元素的位置。而递推的计算顺序是，（假设我们先遍历到了元素 2，然后遍历到了元素 4，两个元素属于不同的子序列）一会计算一下「最后两项模 k 分别为 y 和 2 的子序列」，一会又计算一下「最后两项模 k 分别为 y 和 4 的子序列」，这是「多线程」，没有查找元素位置的过程，遇到谁就处理谁。
class Solution {
public int maximumLength(int[] nums, int k) {
// 初始化最大长度为0
int ans = 0;
// 创建二维DP数组
// f[y][x]表示最后两项模k分别为y和x的子序列的长度
int[][] f = new int[k][k];
// 遍历数组中的每个元素
for (int x : nums) {
// 计算当前元素模k的结果
x %= k;
// 尝试将当前元素添加到以各种可能值结尾的子序列中
for (int y = 0; y < k; y++) {
// 核心递推关系：
// 以y和x结尾的子序列长度 = 以x和y结尾的子序列长度 + 1
// 这表示在以x和y结尾的子序列后添加当前元素x
f[y][x] = f[x][y] + 1;
// 更新最大长度
ans = Math.max(ans, f[y][x]);
}
}
// 返回最长有效子序列的长度
return ans;
}
}
方法二：枚举余数，考察子序列的最后一项 🔍
核心思路
这种方法的核心思想是枚举所有可能的相邻元素之和模 k 的结果 m（从 0 到 k-1），然后对每个 m 分别寻找最长的有效子序列。对于固定的 m，如果子序列的最后一项模 k 为 x，那么倒数第二项模 k 必须为 (m-x) mod k。
实例解析
以 nums=[1,2,1,2,1,2]，k=3，m=1 为例：
- 模 3 后的数组为 [1,2,1,2,1,2]
- 对于 m=1，相邻元素之和模 3 应为 1
- 处理第一个元素 1（模 3 后为 1）：
需要找到倒数第二项模 3 为 (1-1) mod 3 = 0 的子序列
不存在这样的子序列，所以 f[1] = 0 + 1 = 1 - 处理第二个元素 2（模 3 后为 2）：
需要找到倒数第二项模 3 为 (1-2) mod 3 = 2 的子序列
不存在这样的子序列，所以 f[2] = 0 + 1 = 1 - 处理第三个元素 1（模 3 后为 1）：
需要找到倒数第二项模 3 为 (1-1) mod 3 = 0 的子序列
不存在这样的子序列，所以 f[1] 保持为 1 - 处理第四个元素 2（模 3 后为 2）：
需要找到倒数第二项模 3 为 (1-2) mod 3 = 2 的子序列
存在这样的子序列（第三个元素），所以 f[2] = f[2] + 1 = 2 - 依此类推，最终我们可以得到长度为 6 的有效子序列
算法步骤
- 初始化最大长度为 0
- 枚举所有可能的模值 m（从 0 到 k-1）：
a. 创建一个长度为 k 的一维数组 f，f[x] 表示最后一项模 k 为 x 的子序列的长度
b. 遍历数组中的每个元素 x，计算 x mod k
c. 计算倒数第二项应该有的模值：prev = (m - x + k) % k
d. 更新 f[x] = f[prev] + 1
e. 跟踪 f 中的最大值作为当前 m 下的答案 - 返回所有 m 下的最大答案
为什么这样可行？
对于固定的 m，有效子序列中每个相邻元素对 (a,b) 都满足 (a+b) mod k = m。当我们添加一个新元素 x 时，只需要找到以 (m-x) mod k 结尾的子序列，并将 x 添加到其末尾，就能形成一个新的有效子序列。
class Solution {
public int maximumLength(int[] nums, int k) {
// 初始化最大长度为0
int ans = 0;
// 枚举所有可能的相邻元素之和模k的结果m
for (int m = 0; m < k; m++) {
// 创建一维DP数组
// f[x]表示最后一项模k为x的子序列的长度
int[] f = new int[k];
// 遍历数组中的每个元素
for (int x : nums) {
// 计算当前元素模k的结果
x %= k;
// 计算倒数第二项应该有的模值
// (m - x + k) % k 确保结果非负
int prev = (m - x + k) % k;
// 更新f[x]: 在以prev结尾的子序列后添加当前元素x
f[x] = f[prev] + 1;
// 更新最大长度
ans = Math.max(ans, f[x]);
}
}
// 返回最长有效子序列的长度
return ans;
}
}
方法三：贪心算法 + 哈希表 🚀
核心思路
这种方法的核心思想是对于每个可能的模值对 (a,b)，其中 (a+b) % k = m，我们尝试构建最长的交替序列 a,b,a,b,… 或 b,a,b,a,…。我们可以使用哈希表记录每个模值出现的位置，然后对于每个可能的模值对，计算它们能形成的最长序列。
算法步骤
- 创建一个哈希表，记录每个模值出现的所有索引位置
- 初始化最大长度为 0
- 对于每个可能的模值对 (a,b)，其中 (a+b) % k = m（m 从 0 到 k-1）：
a. 使用双指针分别遍历 a 和 b 的位置列表
b. 交替选择 a 和 b 的位置，确保它们在原数组中的顺序
c. 计算能形成的最长序列长度
d. 更新最大长度 - 返回最大长度
代码实现
class Solution {
public int maximumLength(int[] nums, int k) {
// 创建哈希表记录每个模值出现的位置
Map<Integer, List<Integer>> modPositions = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int mod = nums[i] % k;
modPositions.computeIfAbsent(mod, key -> new ArrayList<>()).add(i);
}
int maxLen = 0;
// 枚举所有可能的模值对(a,b)，使得(a+b) % k = m
for (int m = 0; m < k; m++) {
// 获取所有可能的模值
Set<Integer> mods = modPositions.keySet();
// 情况1：序列中只有一种元素
for (int a : mods) {
if ((2 * a) % k == m) {
// 如果a+a的模为m，则可以使用所有a元素
maxLen = Math.max(maxLen, modPositions.get(a).size());
}
}
// 情况2：序列中交替出现两种元素a和b
List<Integer> modList = new ArrayList<>(mods);
for (int i = 0; i < modList.size(); i++) {
int a = modList.get(i);
int b = (m - a + k) % k;
if (!modPositions.containsKey(b)) continue;
// 使用双指针查找最长交替序列
List<Integer> aPositions = modPositions.get(a);
List<Integer> bPositions = modPositions.get(b);
int len1 = getMaxAlternatingLength(aPositions, bPositions); // a开头
int len2 = getMaxAlternatingLength(bPositions, aPositions); // b开头
maxLen = Math.max(maxLen, Math.max(len1, len2));
}
}
return maxLen;
}
// 计算以first开头，交替选择first和second的最长序列长度
private int getMaxAlternatingLength(List<Integer> first, List<Integer> second) {
int i = 0, j = 0;
int len = 0;
boolean chooseFirst = true;
while (i < first.size() || j < second.size()) {
if (chooseFirst) {
if (i >= first.size()) break;
len++;
int lastIdx = first.get(i++);
// 找到第二个列表中比lastIdx大的第一个元素
while (j < second.size() && second.get(j) <= lastIdx) j++;
chooseFirst = false;
} else {
if (j >= second.size()) break;
len++;
int lastIdx = second.get(j++);
// 找到第一个列表中比lastIdx大的第一个元素
while (i < first.size() && first.get(i) <= lastIdx) i++;
chooseFirst = true;
}
}
return len;
}
}
复杂度分析
- 时间复杂度：O(k² + n + k * n)，其中 n 是数组长度，k 是给定的模数值
- O(n)：构建哈希表
- O(k²)：枚举所有可能的模值对
- O(k * n)：双指针遍历位置列表
- 空间复杂度：O(n)，存储每个模值的位置列表
方法比较
这种方法在 k 较小时表现良好，但当 k 较大时（接近 n），时间复杂度会接近 O(n²)，不如前两种方法高效。不过它提供了一种不同的思路，通过预存储位置信息来构建最长序列。
🚀 算法复杂度分析
方法一复杂度
- 时间复杂度：O(nk)，其中 n 是数组长度，k 是给定的模数值
- 空间复杂度：O(k²)，需要维护一个 k×k 的二维数组
方法二复杂度
- 时间复杂度：O(nk)，需要枚举 k 种可能的模值 m，每种模值下遍历数组一次
- 空间复杂度：O(k)，只需维护一个长度为 k 的一维数组
📊 示例分析
示例 1：nums = [1,2,1,2,1,2], k = 3
- 所有元素模 3 后为[1,2,1,2,1,2]
- 方法一：通过 f[y][x] = f[x][y] + 1 不断更新
- f[2][1] = 1 (处理第一个 1)
- f[1][2] = 2 (处理第一个 2)
- f[2][1] = 3 (处理第二个 1)
- f[1][2] = 4 (处理第二个 2)
- 最终得到最大长度 6
- 方法二：枚举 m=0,1,2
- 当 m=0 时，得到序列长度 2
- 当 m=1 时，得到序列长度 6
- 当 m=2 时，得到序列长度 2
- 最终得到最大长度 6
示例 2：nums = [3,1,3,3,2], k = 5
- 所有元素模 5 后为[3,1,3,3,2]
- 最长有效子序列为[3,3,3]，长度 3
- 相邻元素之和模 5 均为 1 (3+3=6%5=1, 3+3=6%5=1)
💡 拓展思考
问题变体
- 如果要求子序列中相邻元素之和的余数等于某个特定值 m（而不只是所有余数相等），该如何解决？
- 如果允许子序列中有一个"错误"（即有一处相邻元素之和的余数与其他不同），最长有效子序列的长度会是多少？
实际应用
这个问题在时间序列分析和模式识别中有实际应用。例如，在分析周期性数据时，我们可能需要找到具有特定模式的最长子序列。
算法选择策略
- 方法一空间复杂度较高(O(k²))，但实现简单直观
- 方法二空间复杂度较低(O(k))，但需要枚举所有可能的模值
- 当 k 较小时(如 k<1000)，两种方法均可选择
- 当 k 较大时(如 k>10000)，方法二更适合
📝 总结
本题是 3201 题的扩展，需要处理更一般化的情况。通过数学分析，我们发现有效子序列的偶数项和奇数项分别关于模 k 同余，这一关键洞察帮助我们设计出高效的动态规划解法。
我们介绍了两种主要方法：
- 维护二维数组 f[y][x]记录最后两项模 k 分别为 y 和 x 的子序列长度
- 枚举所有可能的模值 m，维护一维数组 f[x]记录最后一项模 k 为 x 的子序列长度
两种方法均达到 O(nk)的时间复杂度，远优于暴力解法。通过这类问题，我们可以深入理解模运算的性质和动态规划在序列问题中的应用。
希望今天的讲解能帮助你更好地理解这个问题和动态规划的应用！如果你有任何疑问或想法，欢迎在评论区留言讨论。明天见！👋