使数组和能被P整除

1590. 使数组和能被 P 整除

难度中等

给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。

请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

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

示例 1：

输入：nums = [3,1,4,2], p = 6
输出：1
解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 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 整除了。所以我们不需要移除任何元素。

示例 4：

输入：nums = [1,2,3], p = 7
输出：-1
解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。

示例 5：

输入：nums = [1000000000,1000000000,1000000000], p = 3
输出：0

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= p <= 109

同余定理：数论中的重要概念。给定一个正整数m，如果两个整数 $a$ 和 $b$ 满足$a-b$ 能够被m整除，即 $(a-b)/m$ 得到一个整数，那么就称整数 $a$ 与 $b$ 对模 $m$ 同余，记作 $a≡b(mod\quad m)$ 。对模 $m$ 同余是整数的一个等价关系。

• 反身性：$a≡a (mod\quad m)$；

• 对称性：若$a≡b(mod\quad m)$，则$b≡a (mod\quad m)$；

• 传递性：若$a≡b(mod\quad m)$，$b≡c(mod\quad m)$，则$a≡c(mod\quad m)$；

• 同余式相加：若$a≡b(mod\quad m)$，$c≡d(mod\quad m)$，则$a c≡b d(mod\quad m)$；

• 同余式相乘：若$a≡b(mod\quad m)$，$c≡d(mod\quad m)$，则$ac≡bd(mod\quad m)$。

两数a, b 对 p 同余, 则 (a - b) % p = 0.
sum(nums) % p = k
如果 k != 0,  记 sum(nums) = a, 
要求 (a - b) % p = 0, 其中 a % p = k, 
则 b % p = k,  b 为连续的一段 子数组之和. 取最短的 b .

class Solution {
    public int minSubarray(int[] nums, int p) {
        int ans = Integer.MAX_VALUE;
        HashMap<Long, Integer> map = new HashMap<>();
        //用 mod 存储 和 的余数
        long mod = 0;
        for (int num : nums) {
            mod += num;
        }
        mod = mod % p;                                  // 得到余数
        if (mod == 0) {
            return 0;                                   // 如果 余数 为零，就说明整个数组的和是能被整除的！
        }
        long sum = 0;                                   // sum存储的是 nums[0] 到 nums[i]的和，也就是前缀和
        map.put((long) 0, -1);                          // 把 0 设置为 -1，因为数组起始坐标为0
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            long preMod = sum % p;                      // 求出 前缀和 对 p 取余!
            long target = (preMod - mod + p) % p;       // 求出目前的前缀和的模抵消了多少最开始的那个模,其中加p是为了防止模小于0
            if (map.get(target) != null) {
                ans = Math.min(ans, i - map.get(target));
            }
            map.put(preMod, i);                         // 将当前位置的抵消后的前缀和的模存储map中！
        }
        return ans >= nums.length ? -1 : ans;
    }
}

作者：yi-dai-mi-kang-ji-lou
链接：https://leetcode-cn.com/problems/make-sum-divisible-by-p/solution/xiang-xi-zhu-shi-zou-guo-lu-guo-bu-yao-c-8hkm/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

相似题目

和可被k整除的子数组

和为k的子数组

赏

谢谢你请我吃糖果

微信