最近舍友参加了华为软件笔试，我拿到题目后也尝试做了一下，感觉第二题十分巧妙，于是写篇博客记录一下。

题目描述

司机小王到仓库拉货。仓库管理员已经提前将货物打包装箱,并摆成一排。包装箱从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)的解法，给了我很大的启发。

这种解法的基本思路基于如下原理：

  1. 用货物 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

  1. 当多个位置 a、b、c… 满足 Sum[a]%k=Sum[b]%k=Sum[c]%k=… 时，记位置个数为 t ，在这些位置中任意挑选两个位置即可构成一个满足条件的区间，因此此时满足条件的区间个数为 C(t,2) 。

C(t,2)是数学排列组合，展开为 t*(t-1)/2 。

具体操作如下：

  1. 使用长度为 n 的数组 M 存储仓库货物数，输入完毕后另开一个长度为 n 的数组 Sum，令 Sum[i] 表示 M[0]+M[1]+…+M[i]，此时 Sum[j]-Sum[i] 表示货物 i 到货物 j 的区间货物总数。

  2. 开一个长度为 k 的数组 count ，遍历 Sum 数组，对任意 0 - n 间的索引 x，使 count[Sum[x]%k]+=1。

  3. 遍历 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 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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)
}