Medium

题目描述

给你一个整数数组 nums 和一个正整数 k。

长度为 x 的 nums 子序列 sub 被称为有效的，当且仅当满足：

(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k

返回 nums 的最长有效子序列的长度。

示例 1：

输入：nums = [1,2,3,4,5], k = 2
输出：5
解释：最长有效子序列是 [1, 2, 3, 4, 5]。

示例 2：

输入：nums = [1,4,2,3,1,4], k = 3
输出：4
解释：最长有效子序列是 [1, 4, 1, 4]。

提示：

  • 2 <= nums.length <= 10³
  • 1 <= nums[i] <= 10⁷
  • 1 <= k <= 10³

解题思路

这是一个经典的动态规划问题。核心思路是理解有效子序列的性质：相邻元素的和对 k 取模必须保持一致。

核心观察： 如果子序列中相邻元素和的模数固定为 val，那么对于当前元素 nums[i] % k = r，下一个元素的模数必须是 (val - r) % k。

算法思路：

  1. 枚举所有可能的模数值：遍历所有可能的相邻和模数 val（0到k-1）
  2. 状态定义：dp[r] 表示以模数为 r 的元素结尾的最长有效子序列长度
  3. 状态转移：对于当前元素 nums[i] % k = r，它可以接在模数为 (val - r + k) % k 的元素后面
  4. 更新答案：对于每个 val，找出对应的最长子序列长度

具体步骤：

  • 对每个可能的 val，初始化 dp 数组
  • 遍历数组中的每个元素，计算其模数 r = nums[i] % k
  • 找到可以接在当前元素前面的元素模数：prev = (val - r + k) % k
  • 更新：dp[r] = max(dp[r], dp[prev] + 1)

时间复杂度为 O(n×k)，空间复杂度为 O(k)。

代码实现

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = 0;
        
        // 枚举所有可能的相邻和模数
        for (int val = 0; val < k; val++) {
            vector<int> dp(k, 0);
            
            for (int i = 0; i < n; i++) {
                int r = nums[i] % k;
                int prev = (val - r + k) % k;
                dp[r] = max(dp[r], dp[prev] + 1);
            }
            
            // 找出当前val下的最大长度
            for (int i = 0; i < k; i++) {
                ans = max(ans, dp[i]);
            }
        }
        
        return ans;
    }
};

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        ans = 0
        
        # 枚举所有可能的相邻和模数
        for val in range(k):
            dp = [0] * k
            
            for num in nums:
                r = num % k
                prev = (val - r + k) % k
                dp[r] = max(dp[r], dp[prev] + 1)
            
            # 找出当前val下的最大长度
            ans = max(ans, max(dp))
        
        return ans

public class Solution {
    public int MaximumLength(int[] nums, int k) {
        int n = nums.Length;
        int ans = 0;
        
        // 枚举所有可能的相邻和模数
        for (int val = 0; val < k; val++) {
            int[] dp = new int[k];
            
            for (int i = 0; i < n; i++) {
                int r = nums[i] % k;
                int prev = (val - r + k) % k;
                dp[r] = Math.Max(dp[r], dp[prev] + 1);
            }
            
            // 找出当前val下的最大长度
            for (int i = 0; i < k; i++) {
                ans = Math.Max(ans, dp[i]);
            }
        }
        
        return ans;
    }
}

var maximumLength = function(nums, k) {
    const n = nums.length;
    let ans = 0;
    
    // 枚举所有可能的相邻和模数
    for (let val = 0; val < k; val++) {
        const dp = new Array(k).fill(0);
        
        for (let i = 0; i < n; i++) {
            const r = nums[i] % k;
            const prev = (val - r + k) % k;
            dp[r] = Math.max(dp[r], dp[prev] + 1);
        }
        
        // 找出当前val下的最大长度
        for (let i = 0; i < k; i++) {
            ans = Math.max(ans, dp[i]);
        }
    }
    
    return ans;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × k)需要枚举k个可能的模数值，对每个值遍历n个元素
空间复杂度O(k)使用长度为k的dp数组存储状态

相关题目