LeetCode974. 和可被 K 整除的子数组

╰+哭是因爲堅強的太久メ 2023-01-11 13:01 148阅读 0赞

![LeetCode974][]

# 先从简单开始 #

仔细观察本题要求，如果使用暴力的解法，将导致超时（每一个开头，到每一个结尾枚举，再累加）总计是O（n³）

> 当然，必然不可能轻轻松松使用暴力解决

# 改进算法 #

考虑到题目是列表的区间问题，可以尝试使用滑动窗口或前缀和的方法减少计算量  
若有经验，都能得知这两种方法一般可以把最坏时间降低一级也就是O(n²)

**先用滑动窗口**  
我们固定左侧，让右侧移动，以此遍历所有的可能  
两层for，On方的时间复杂度

class Solution {
        
        public int subarraysDivByK(int[] A, int K) {
        
            if (A.length == 0) {
        
                return 0;
            }
            int count=0;
            for (int i = 0; i < A.length; i++) {
        
                int sum = A[i];
                if (sum % K == 0) {
        
                    count ++;
                }
                for (int j = i+1; j < A.length; j++) {
        
                    sum += A[j];
                    if (sum % K == 0) {
        
                        count ++;
                    }
                }
            }
            return count;
        }
    }

很不幸，超时了，说明On方并不能解决问题  
那尝试升级这个算法呢？滋，说实话想不到什么办法。

### 试试前缀和？ ###

我们尝试使用前缀和，前缀和可以通过关系计算出当前的值，不用再遍历内层。我们通过前缀和计算出从0加到当前为多少，这样不用执行累加操作。  
计算完成后，我们遍历所有可能。  
**前缀和优化问题**

class Solution {
        
        public int subarraysDivByK(int[] A, int K) {
        
            int N = A.length, ans = 0;
            int[] sum = new int[N+1];
    
            for (int i = 0; i < N; i++) {
        
                sum[i+1] = sum[i] + A[i];
            }
    
            for (int i = 0; i < N; i++) {
        
                for (int j = i+1; j <= N; j++) {
        
                    int res = sum[j] - sum[i];
                    if (res % K == 0) ans++;
                }
            }
            return ans ;
        }
    }

自然，算法是N方的，盲猜挂了，果不其然。。  
那么能不能优化这个代码，  
后半段的二重循环是主要原因，我们目光落在这里  
我们遍历了所有的可能，使得 **(sum\[j\] - sum\[i\]) % K == 0**  
现在的目标是找到一种方法，使得**不需要遍历所有组合可能也能判断有几个符合，即找等价**  
回顾所学，似乎有个玩意，能保证不同的式子相减的余相等  
他就是“**同余定理**”（**我是真的不熟悉这个玩意儿**）

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

于是乎

1.  我们要判断(sum\[j\] - sum\[i\]) % K == 0
2.  也就是sum\[j\] %K - sum\[i\] %K ==0
3.  也就是sum\[j\] %K == sum\[i\] %K
4.  推到这里，我们可以总结，只要sum\[i\]%K存在相同的可能，就会出现一个满足的区间
5.  所以我们只需要知道sum\[j\] %K有几个值了就够了
6.  每一个配对的sum\[j\] %K == sum\[i\] %K 都能增加1个结果

在编写的时候，我们发现，0或者K不需要一个队友，也能算一个，所以我们提前塞一个进去record.put(0, 1);  
于是，我们得到下面的代码

public class LeetCode974 {
        
        public int subarraysDivByK(int[] A, int K) {
        
            Map<Integer, Integer> record = new HashMap<>();
            record.put(0, 1);
            int sum = 0, ans = 0;
            for (int elem: A) {
        
                sum += elem;
                // 注意 Java 取模的特殊性，当被除数为负数时取模结果为负数，需要纠正
                int modulus = (sum % K + K) % K;
                int same = record.getOrDefault(modulus, 0);
                ans += same;
                record.put(modulus, same + 1);
            }
            return ans;
        }
        
    }

AC快乐

[LeetCode974]: /images/20221119/bf9533fe912a40589816c3b221d4c86f.png