能被 K 整除的最大連續子串長度

【來源】網上流傳的2017美團秋招筆試題

【問題描述】

  兩個測試樣例輸出都是5

【算法思路】

暴力解法時間會超限，使用一種很巧妙的數學方法。用在讀取數組arr時用數組sum記錄其前 i 項的和，即 sum[i] = arr[1]+arr[2]+...+arr[i]。利用這一個數學性質：假設前m項之和被 K 除後餘數是 x, 前n項之和被 K 除後餘數也是 x, 則m+1-n的子序列之和肯定能被K整除。

【代碼】

1 #include<iostream>
 2 #include<algorithm>
 3 #define MAXN 100005
 4 using namespace std;
 5 
 6 int sum[MAXN];
 7 int arr[MAXN];
 8 int pos[MAXN];
 9 int main() {
10 
11     int N,K;
12     cin >> N;
13 
14     for (size_t i = 1; i <=N; i++) {
15         cin >> arr[i];
16         sum[i] = sum[i - 1] + arr[i];
17     }
18     cin >> K;
19     fill(pos, pos + MAXN, INT_MAX);
20     int maxL = 0;
21     for (int i = 1; i <=N; i++) {
22         int m = sum[i] % K;
23         if (m == 0)
24             maxL = max(maxL, i);
25         if (pos[m] != INT_MAX) {
26             maxL = max(maxL, i - pos[m]);
27         }
28         pos[m] = min(pos[m], i);
29     }
30     cout << maxL << endl;
31     return 0;
32 }