974这题，负数取余的问题

先求前缀和，

再对前缀和求余数，

最后对同样余数的数，做排列组合。

1. class Solution {
   
2. 
   
3.     public int subarraysDivByK(int[] A, int K) {
   
4. 
   
5.         int N = A.length;
   
6. 
   
7.         int[] P = new int[N + 1];
   
8. 
   
9.         for (int i = 0; i < N; ++i) P[i + 1] = P[i] + A[i];
   
10. 
    
11.         int[] count = new int[K];
    
12. 
    
13.         for (int x : P) {
    
14.             
    
15.             count[ (x % K + K) % K ]++;   
    
16.         }
    
17. 
    
18.         int ans = 0;
    
19. 
    
20.         for (int v : count)
    
21.             ans += v * (v - 1) / 2;
    
22.         
    
23.         return ans;
    
24.     }   
    
25. }

复制代码

有人知道为何求余数，要用这个方式求吗？  

(x % K + K) % K

你都知道是负数的问题了。
(-5) % 3 == -2
((-5) % 3 + 3) % 3 == 1
数组下标非负。

X % K 有可能出现负数，加上K后结果肯定是正数，再取余数保证数组下标不出现负数（越界）情况。
对于正数来说，由于 K % K = 0，所以加上 K 不影响计算结果

usr_opta 发表于 2020-12-23 13:03
你都知道是负数的问题了。
(-5) % 3 == -2
((-5) % 3 + 3) % 3 == 1

数组下标非负  --> 这是什么意思?

techDiscussion 发表于 2020-12-23 01:10
数组下标非负  --> 这是什么意思?

(-5) % 3 == -2
你不能取count[-2]啊，所以要加个K变成1再取count[1]