Leetcode 1590. Make Sum Divisible by P

Tyan

发布于 2021-08-10 10:44:08

3750

发布于 2021-08-10 10:44:08

文章被收录于专栏：SnailTyan

文章作者：Tyan 博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

**解析：**Version 1，使用前缀和来解决，先对整个数组求和，总和与p的余数设为k，如果k==0，则直接返回0即可。否则，将遍历数组，求前缀和，前缀和与p的余数设为remainder，题目需要移除的部分是两个前缀和相减后的部分，其与p的余数应为k，即(remainder - temp) % p == k，temp是需要寻找的余数，由于remainder - temp为负数时，公式变为p + remainder - temp = k，通过公式变换，可以得到temp = p + remainder - k，由于remainder - temp大于0时不需要加上p，因此公式变为temp = (remainder + p - k) % p。字典中保持的是余数及对应的位置索引，由于余数相同时索引位置更新，因此字典中保存的永远余数相同时是最大的位置索引，这样可以保证满足条件时要移除的元素数量最少。注意，假设第一个数的余数就等于k，此时数组中没有要寻找的余数temp=0的位置，因此stat[0]=-1，这样计算的长度才不会错。初始长度设为数组长度，如果没找到满足条件的子数组，则长度不更新，此时将长度设为-1。

Version 1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        k = sum(nums) % p
        if k == 0:
            return 0
        total = 0
        stat = collections.defaultdict(int)
        stat[0] = -1
        length = len(nums)
        for i in range(len(nums)):
            total += nums[i]
            remainder = total % p
            temp = (remainder + p - k) % p
            if temp in stat:
                length = min(length, i - stat[temp])
            stat[remainder] = i
        if length == len(nums):
            length = -1
        return length