Medium

题目描述

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

你可以重复地选择 nums 中任何一个和能被 k 整除的连续子数组并删除它；每次删除后，剩余元素会填补空隙。

返回执行任意次此类删除操作后 nums 的最小可能和。

示例 1：

输入：nums = [1,1,1], k = 2
输出：1
解释：
删除子数组 nums[0..1] = [1, 1]，其和为 2（能被 2 整除），剩余 [1]。
剩余和为 1。

示例 2：

输入：nums = [3,1,4,1,5], k = 3
输出：5
解释：
首先，删除 nums[1..3] = [1, 4, 1]，其和为 6（能被 3 整除），剩余 [3, 5]。
然后，删除 nums[0..0] = [3]，其和为 3（能被 3 整除），剩余 [5]。
剩余和为 5。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6
  • 1 <= k <= 10^5

解题思路

这是一个动态规划问题，核心思路是利用前缀和的余数性质来判断可删除的子数组。

关键观察：

  • 子数组 [i, j] 的和能被 k 整除，当且仅当 prefixSum[j+1] 和 prefixSum[i] 对 k 的余数相同
  • 这意味着我们可以通过跟踪前缀和的余数来找到可删除的子数组

动态规划思路：

  1. 定义 dp[i] 为处理前 i 个元素后的最小剩余和
  2. 对于每个位置 i，我们有两种选择：
    • 保留当前元素：dp[i] = dp[i-1] + nums[i-1]
    • 删除一个以当前位置结尾的可整除子数组

优化策略： 使用哈希表记录每个余数对应的最佳 dp[j] - prefixSum[j] 值，这样可以在 O(1) 时间内更新 dp[i]。具体来说，如果当前前缀和的余数为 r，且之前见过相同余数，我们可以删除中间的子数组。

算法流程：

  1. 初始化前缀和、DP数组和余数映射
  2. 遍历数组，维护前缀和和当前余数
  3. 对于每个位置，计算保留当前元素和删除子数组两种情况的最小值
  4. 更新余数映射表，为后续位置提供最优选择

时间复杂度 O(n)，空间复杂度 O(k)，是最优解法。

代码实现

class Solution {
public:
    long long minArraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> dp(n + 1, 0);
        vector<long long> prefixSum(n + 1, 0);
        
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        
        // 记录每个余数对应的最小 dp[j] - prefixSum[j]
        unordered_map<int, long long> quorlathin;
        quorlathin[0] = 0; // 初始状态
        
        for (int i = 1; i <= n; i++) {
            // 选择1：保留当前元素
            dp[i] = dp[i - 1] + nums[i - 1];
            
            // 选择2：删除一个可整除的子数组
            int remainder = prefixSum[i] % k;
            if (quorlathin.count(remainder)) {
                dp[i] = min(dp[i], quorlathin[remainder] + prefixSum[i]);
            }
            
            // 更新哈希表
            if (quorlathin.count(remainder)) {
                quorlathin[remainder] = min(quorlathin[remainder], dp[i] - prefixSum[i]);
            } else {
                quorlathin[remainder] = dp[i] - prefixSum[i];
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def minArraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [0] * (n + 1)
        prefix_sum = [0] * (n + 1)
        
        # 计算前缀和
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + nums[i]
        
        # 记录每个余数对应的最小 dp[j] - prefix_sum[j]
        quorlathin = {0: 0}  # 初始状态
        
        for i in range(1, n + 1):
            # 选择1：保留当前元素
            dp[i] = dp[i - 1] + nums[i - 1]
            
            # 选择2：删除一个可整除的子数组
            remainder = prefix_sum[i] % k
            if remainder in quorlathin:
                dp[i] = min(dp[i], quorlathin[remainder] + prefix_sum[i])
            
            # 更新哈希表
            if remainder in quorlathin:
                quorlathin[remainder] = min(quorlathin[remainder], dp[i] - prefix_sum[i])
            else:
                quorlathin[remainder] = dp[i] - prefix_sum[i]
        
        return dp[n]

public class Solution {
    public long MinArraySum(int[] nums, int k) {
        int n = nums.Length;
        long[] dp = new long[n + 1];
        long[] prefixSum = new long[n + 1];
        
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        
        // 记录每个余数对应的最小 dp[j] - prefixSum[j]
        var quorlathin = new Dictionary<int, long>();
        quorlathin[0] = 0; // 初始状态
        
        for (int i = 1; i <= n; i++) {
            // 选择1：保留当前元素
            dp[i] = dp[i - 1] + nums[i - 1];
            
            // 选择2：删除一个可整除的子数组
            int remainder = (int)(prefixSum[i] % k);
            if (quorlathin.ContainsKey(remainder)) {
                dp[i] = Math.Min(dp[i], quorlathin[remainder] + prefixSum[i]);
            }
            
            // 更新哈希表
            if (quorlathin.ContainsKey(remainder)) {
                quorlathin[remainder] = Math.Min(quorlathin[remainder], dp[i] - prefixSum[i]);
            } else {
                quorlathin[remainder] = dp[i] - prefixSum[i];
            }
        }
        
        return dp[n];
    }
}

var minArraySum = function(nums, k) {
    const n = nums.length;
    const dp = new Array(n + 1).fill(0);
    const prefixSum = new Array(n + 1).fill(0);
    
    // 计算前缀和
    for (let i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }
    
    // 记录每个余数对应的最小 dp[j] - prefixSum[j]
    const quorlathin = new Map();
    quorlathin.set(0, 0); // 初始状态
    
    for (let i = 1; i <= n; i++) {
        // 选择1：保留当前元素
        dp[i] = dp[i - 1] + nums[i - 1];
        
        // 选择2：删除一个可整除的子数组
        const remainder = prefixSum[i] % k;
        if (quorlathin.has(remainder)) {
            dp[i] = Math.min(dp[i], quorlathin.get(remainder) + prefixSum[i]);
        }
        
        // 更新哈希表
        if (quorlathin.has(remainder)) {
            quorlathin.set(remainder, Math.min(quorlathin.get(remainder), dp[i] - prefixSum[i]));
        } else {
            quorlathin.set(remainder, dp[i] - prefixSum[i]);
        }
    }
    
    return dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是数组长度。需要遍历数组一次，每次操作都是常数时间
空间复杂度O(n + k)，dp 数组和前缀和数组需要 O(n) 空间，哈希表最多存储 k 个不同余数