Medium

题目描述

给定一个正整数数组 nums，删除最小的子数组（可能为空），使剩余元素的和能被 p 整除。不允许删除整个数组。

返回你需要删除的最小子数组的长度，如果不可能，返回 -1。

子数组定义为数组中连续的元素块。

示例 1：

输入：nums = [3,1,4,2], p = 6
输出：1
解释：nums 中元素的和为 10，不能被 6 整除。我们可以删除子数组 [4]，剩余元素的和为 6，能被 6 整除。

示例 2：

输入：nums = [6,3,5,2], p = 9
输出：2
解释：我们不能删除一个元素来得到能被 9 整除的和。最好的方法是删除子数组 [5,2]，留下 [6,3]，和为 9。

示例 3：

输入：nums = [1,2,3], p = 3
输出：0
解释：这里和为 6，已经能被 3 整除。因此我们不需要删除任何元素。

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= p <= 10^9

解题思路

解题思路

这道题的关键在于理解数学关系：如果要让剩余数组的和能被 p 整除，我们需要找到一个子数组，其和的余数等于原数组总和的余数。

核心思路：

  1. 计算目标余数：设原数组总和为 total，目标余数 target = total % p。如果 target = 0，则无需删除任何元素。

  2. 前缀和与余数：使用前缀和数组，对于子数组 nums[i...j]，其和为 prefix[j+1] - prefix[i]。要使这个子数组的和模 p 等于 target，需要：

    (prefix[j+1] - prefix[i]) % p = target

    即：prefix[i] % p = (prefix[j+1] - target) % p

  3. 哈希表优化：使用哈希表记录每个前缀和余数最近出现的位置，这样可以在 O(1) 时间内找到符合条件的起始位置。

  4. 边界处理：初始化时在哈希表中放入 {0: -1}，表示空前缀的情况。

算法流程：

  • 计算总和的余数 target
  • 遍历数组，维护前缀和的余数
  • 对每个位置，查找是否存在之前的位置使得子数组余数为 target
  • 记录最小的子数组长度

时间复杂度： O(n)
空间复杂度： O(min(n, p))

代码实现

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        int n = nums.size();
        long long total = 0;
        for (int num : nums) {
            total += num;
        }
        
        int target = total % p;
        if (target == 0) return 0;
        
        unordered_map<int, int> modMap;
        modMap[0] = -1;
        
        long long prefixSum = 0;
        int minLen = n;
        
        for (int i = 0; i < n; i++) {
            prefixSum += nums[i];
            int currentMod = prefixSum % p;
            int needMod = (currentMod - target + p) % p;
            
            if (modMap.count(needMod)) {
                minLen = min(minLen, i - modMap[needMod]);
            }
            
            modMap[currentMod] = i;
        }
        
        return minLen == n ? -1 : minLen;
    }
};

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        target = sum(nums) % p
        if target == 0:
            return 0
        
        mod_map = {0: -1}
        prefix_sum = 0
        min_len = len(nums)
        
        for i, num in enumerate(nums):
            prefix_sum += num
            current_mod = prefix_sum % p
            need_mod = (current_mod - target) % p
            
            if need_mod in mod_map:
                min_len = min(min_len, i - mod_map[need_mod])
            
            mod_map[current_mod] = i
        
        return -1 if min_len == len(nums) else min_len

public class Solution {
    public int MinSubarray(int[] nums, int p) {
        int n = nums.Length;
        long total = 0;
        foreach (int num in nums) {
            total += num;
        }
        
        int target = (int)(total % p);
        if (target == 0) return 0;
        
        Dictionary<int, int> modMap = new Dictionary<int, int>();
        modMap[0] = -1;
        
        long prefixSum = 0;
        int minLen = n;
        
        for (int i = 0; i < n; i++) {
            prefixSum += nums[i];
            int currentMod = (int)(prefixSum % p);
            int needMod = (currentMod - target + p) % p;
            
            if (modMap.ContainsKey(needMod)) {
                minLen = Math.Min(minLen, i - modMap[needMod]);
            }
            
            modMap[currentMod] = i;
        }
        
        return minLen == n ? -1 : minLen;
    }
}

/**
 * @param {number[]} nums
 * @param {number} p
 * @return {number}
 */
var minSubarray = function(nums, p) {
    const totalSum = nums.reduce((sum, num) => sum + num, 0);
    const target = totalSum % p;
    
    if (target === 0) return 0;
    
    const map = new Map();
    map.set(0, -1);
    
    let prefixSum = 0;
    let minLen = nums.length;
    
    for (let i = 0; i < nums.length; i++) {
        prefixSum = (prefixSum + nums[i]) % p;
        const needed = (prefixSum - target + p) % p;
        
        if (map.has(needed)) {
            minLen = Math.min(minLen, i - map.get(needed));
        }
        
        map.set(prefixSum, i);
    }
    
    return minLen === nums.length ? -1 : minLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组一次，每次操作都是常数时间
空间复杂度O(min(n, p))哈希表最多存储 min(n, p) 个不同的余数

相关题目