最近舍友参加了华为软件笔试，我拿到题目后也尝试做了一下，感觉第二题十分巧妙，于是写篇博客记录一下。
题目描述#
司机小王到仓库拉货。仓库管理员已经提前将货物打包装箱，并摆成一排。包装箱从 1 开始编号。各个包装箱存放的货物数组成一个集合 M={M1, M2. ..., Mn}。货车一次最多运送 K 件货物。为了最大化动力，小王想一次从中挑选出 K 的整数倍件货物，再分批运输。仓库管理员为了方便管理，要求小王必须选择编号连续的包装箱，如可选择 1、2、3 号箱，不能选择 2、4、6 号箱。
如果运输 K 整数倍件货物，请帮小王计算有多少种挑选方式。
输入描述#
包装箱数为 N，货车一次运送货物的最大数为 K
各箱子存放的货物数：M1, M2, M3, M4, ...
输入为二行，格式如下：
N K
MI M2 M3 M4 ...
N 和 K 的取值范围皆为 [1, 100000]
第 i 个包装箱存放货物数的取值范围也是 [1, 100000]
分析#
因为是连续序列问题，所以开始我考虑使用的是滑动窗口，但分析后发现不可行。
滑动窗口的一般方法是首先扩大窗口，当出现某种情况使窗口不能满足条件时再缩小窗口。但该题不同在于：无法通过局部条件判断需要缩小窗口，即不可能因为当前窗口不满足 k 的整数倍就能保证继续扩大窗口后不能满足 k 的整数倍。
接着我又想到使用动态规划对区间求和，然后遍历判断各个区间是否符合条件。经验告诉我们这是正确的，但动态规划需要一个二维数组标记区间和，空间复杂度为 O (N^2)，同时需要遍历该二维数组，时间复杂度也为 O (N^2)，在 N 取值范围为 [1,100000] 的情况下，这样的复杂度是我们不能接受的。
遍历枚举？虽然降低了空间复杂度，但时间复杂度比动态规划还要高得多，更加无法接受。
遇事不决看题解，随便找了几个题解看，这篇题解给出了一种时间复杂度为 O (n+k) 的解法，给了我很大的启发。
这种解法的基本思路基于如下原理：
- 用货物 0-j 的和与货物 0-i 的和做差，得到的差是货物 i-j 的和，如果该和可以被 k 整除，即货物 0-j 的和模 k 等于货物 0-i 的和模 k，则该区间满足条件。
该结论的数学表示是：
(Sum[j]-Sum[i])%k=0 => Sum[j] = n*k + Sum[i] => Sum[j]%k = Sum[i]%k
- 当多个位置 a、b、c... 满足 Sum [a]% k=Sum [b]% k=Sum [c]% k=... 时，记位置个数为 t ，在这些位置中任意挑选两个位置即可构成一个满足条件的区间，因此此时满足条件的区间个数为 C (t,2) 。
C (t,2) 是数学排列组合，展开为 t*(t-1)/2 。
具体操作如下：
-
使用长度为 n 的数组 M 存储仓库货物数，输入完毕后另开一个长度为 n 的数组 Sum，令 Sum [i] 表示 M [0]+M [1]+...+M [i]，此时 Sum [j]-Sum [i] 表示货物 i 到货物 j 的区间货物总数。
-
开一个长度为 k 的数组 count ，遍历 Sum 数组，对任意 0 - n 间的索引 x，使 count [Sum [x]% k]+=1。
-
遍历 count 数组，对任意 0 - k 间的索引 y，如果 count [y]>1，则 result = result + C (count [y],2)，最后返回 result 。
在实际代码表示中，我们可以省去 M 和 Sum 数组，在输入的同时对 count 进行相关操作。这样的话，我们只需要处理 n 个输入，遍历长度为 k 的数组，时间复杂度为 O (n+k) ，同时只使用了一个长度为 k 的 count 数组，空间复杂度为 O (k) ，是该问题的最优解。
代码#
我的 Golang 代码如下：
package main
import "fmt"
func main() {
var (
n, k int
tmp int
current int
count []int
result int
)
fmt.Scanln(&n, &k)
count = make([]int, k)
// 输入货物列表，实时累加
for i := 0; i < n; i++ {
fmt.Scan(&tmp)
current = (current + tmp) % k
count[current] += 1
}
for _, v := range count {
if v > 1 {
result += v * (v - 1) / 2
}
}
fmt.Println(result)
}