LeetCode 1590. 使数组和能被 P 整除

Categories:

题目描述
思路分析
1. 解法一：前缀和 + 哈希表（推荐）
相似题目

题目描述

✅ 1590. 使数组和能被 P 整除

思路分析

解法一：前缀和 + 哈希表（推荐）

核心思路：

设数组总和为 total，若 total % p == 0 直接返回 0

需要找最短子数组，使其元素和 ≡ total % p (mod p)，删除后剩余部分能整除 p

维护前缀和模 p 的哈希表：prefixMod → 最新下标

对每个位置 i，当前前缀和模为 cur，目标前缀和模为 need = (cur - target + p) % p

若哈希表中存在 need，则子数组长度为 i - map[need]，更新最小长度

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，单次遍历

空间复杂度：O(n)，哈希表最多存储 n 个前缀和

class Solution {
    public int minSubarray(int[] nums, int p) {
        int n = nums.length;
        int total = 0;

        // 计算数组总和模 p
        for (int num : nums) {
            total = (total + num) % p;
        }

        // 总和已整除 p，无需删除
        if (total == 0) {
            return 0;
        }

        // 哈希表：前缀和模 p → 最新下标
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);

        int cur = 0;
        int ans = n;

        for (int i = 0; i < n; i++) {
            cur = (cur + nums[i]) % p;

            // 需要找到前缀和模为 need 的位置
            int need = (cur - total + p) % p;

            if (map.containsKey(need)) {
                ans = Math.min(ans, i - map.get(need));
            }

            map.put(cur, i);
        }

        // 不能删除整个数组
        return ans < n ? ans : -1;
    }
}

func minSubarray(nums []int, p int) int {
    n := len(nums)
    total := 0

    // 计算数组总和模 p
    for _, num := range nums {
        total = (total + num) % p
    }

    // 总和已整除 p，无需删除
    if total == 0 {
        return 0
    }

    // 哈希表：前缀和模 p → 最新下标
    prefixMap := map[int]int{0: -1}
    cur := 0
    ans := n

    for i, num := range nums {
        cur = (cur + num) % p

        // 需要找到前缀和模为 need 的位置
        need := (cur - total + p) % p

        if j, ok := prefixMap[need]; ok {
            if i-j < ans {
                ans = i - j
            }
        }

        prefixMap[cur] = i
    }

    // 不能删除整个数组
    if ans < n {
        return ans
    }
    return -1
}

相似题目

题目	难度	考察点
523. 连续的子数组和	中等	前缀和、哈希表
974. 和可被 K 整除的子数组	中等	前缀和、哈希表
560. 和为 K 的子数组	中等	前缀和、哈希表
525. 连续数组	中等	前缀和、哈希表
1010. 总持续时间可被 60 整除的歌曲	中等	哈希表、取模
1248. 统计「优美子数组」	中等	前缀和、哈希表

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/86019240