Skip to content

Commit 118bcb7

Browse files
authored
Update Readme.md
1 parent e211d41 commit 118bcb7

1 file changed

Lines changed: 1 addition & 1 deletion

File tree

Hash/1590.Make-Sum-Divisible-by-P/Readme.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,6 @@
22

33
假设整个数组的和除以P的余数是r0. 题目要求subarray的剩余数字和除以P于0,那么就意味着这个subarray sum除以P的余数就是r0. 于是本题就转化成了求最短的subarray,满足和是r0.
44

5-
假设我们探索这样的subarray,令其右边界是j,那么左边界i可以取在哪里呢?我们可以利用前缀和的思想。如果```presum[j]%P==r```,那么我们必然要求```presum[i]%P==r-r0```(当然如果r-r0<0,那么我们就要补上一个周期变成r-r0+P). 所以我们转化为了求与j最接近的索引i,满足presum[i]%P==r-r0。 显然,我们在遍历之前的presum的时候,可以每次都求一下它除以P的余数,然后存下余数->索引的映射关系。此时,我们就可以直接调用Map[r-r0]得到该余数对应的、最近的presum的索引值。
5+
假设我们探索这样的subarray,令其右边界是j,那么左边界i可以取在哪里呢?我们可以利用前缀和的思想。如果```presum[j]%P==r```,那么我们必然要求```presum[i]%P==r-r0```当然如果r-r0<0,那么我们就要补上一个周期变成```r-r0+P```. 所以我们转化为了求与j最接近的索引i,满足```presum[i]%P==r-r0```。 显然,我们在遍历之前的presum的时候,可以每次都求一下它除以P的余数,然后存下余数->索引的映射关系。此时,我们就可以直接调用Map[r-r0]得到该余数对应的、最近的presum的索引值。
66

77
本题要注意,计算totalSum和preSum的过程中,都有可能会溢出。但事实上,所有的操作都和取余有关,所以我们只需要每一步求和都取余就行了。

0 commit comments

Comments
 (0)