[GoogleInterview]连续子序列问题

Before the Beginning

本文为 Clouder 原创文章，原文链接为 https://www.codein.icu/gci-subarray/，转载时请将本段放在文章开头显眼处。如进行了二次创作，请明确标明。

前言

在颓废地水 Telegram 的时候，在 Codeforces 群里看到有人发了张谷歌面试的题的图，还是有那么一些意思的，向神犇求助后有所收获，写一篇题解。
题目难度不大，如何优雅地解决才是问题。

题面

给定一个无序数组 (A)，长度为 (N)，元素皆为非负整数，要求找到一段连续的子序列使得其和为 (S)。

思路

暴力的思路非常简单，枚举左右端点乱搞就是了。复杂度大概是 (O(n^3)) 的。
考虑稍加优化，预处理出前缀和，依然枚举左右端点，复杂度为 (O(n^2))。
这是最直观的想法了，然而要求复杂度为 (O(n))，就必须找到更优的算法。

哈希表法

既然有了前缀和，那么这一段子序列可以用数学语言来表示一下：
(S = s_i - s_j(j leq i))
其中 (s) 代表前缀和。
稍加变换，就可以变为：
(s_i - S = s_j(j leq i))
问题转化为是否存在 (j in [1,i]) 使得 (s_j = s_i - S)。
那么可以顺着扫一遍，判断之前是否有 (s_j = s_i - S)，再将 (s_i) 的值记录下来。
伪代码：

for(int i = 1;i<=n;++i)
{
    s[i] = s[i - 1] + a[i];
    if(map[s[i] - S] != 0)
        return make_pair(map[s[i] - S] + 1,i);
    map[s[i]] = i;
}

那么复杂度的瓶颈就在于这个 map 如何实现了。使用红黑树可以做到稳定的 (O(nlog n))，而使用哈希表可以做到 (O(n))。
然而哈希表的复杂度相当玄学，并且在元素值域过大时表现并不好。
有没有更稳定的、优雅的解决方法呢？

双指针扫描法

这是与神犇讨论后产生的解法，笔者认为相当优雅，并且顺路膜拜了神犇。
双指针扫描发，或者说对撞指针法？网上的资料较少，我只能大致讲一下。
拿经典的两数之和来举例子吧。

首先保证数组有序，要求找到两个数和为定值。
那么初始化左指针为数组开头，右指针为数组末尾。
判断两数相加，若大于目标值，则右指针左移。若小于目标值，则左指针右移。
那么两个指针重合时终止。很容易证明复杂度为 (O(n))。

相信这个还是很容易理解的。
那么这道题，只是将两数之和变成了两数之差，也可以使用相类似的双指针法。
要求：
(S = s_i - s_j(j leq i))
先预处理出前缀和数组，由于元素都是非负整数，前缀和数组天然单调递增。
发现右指针右移时单调递增，左指针右移时单调递减，因此满足了单调性。
如果空数组也是可选的，那么右指针初始和左指针位置相同。
伪代码：

int lp = 0,rp = 0;
while(lp <= rp && lp >= 0 && rp <= n)
{
    if(s[rp] - s[lp] == S)
        return make_pair(lp + 1,rp);
    if(s[rp] - s[lp] < S)
        ++rp;
    else
        ++lp;
}

那么复杂度就是相当稳定的 (O(n))了。

双指针扫描法证明

至于双指针法的正确性，感性理解很容易，但严谨证明，笔者觉得还是有些难度的。(当然是笔者太弱了)
在借鉴了 chend大佬的两数之和正确性证明后，笔者也尝试自证一下。

使用数学归纳法证明算法运行过程中 (forall a in [0,L],b in [L+1,R])，(s_b - s_a eq S)。

初始时，不考虑空数组的情况，从 (L = 0,R = 1) 开始，若成立则算法退出，否则命题成立。
假定 (forall a in [0,L],b in [L+1,R]) 中命题已成立，
欲证 (forall a in [0,L+1],b in [L+2,R]) 中命题成立，
若 (s_{R} - s_{L+1} = S) 则算法结束，因此要证明命题，
即证 (forall b in [L+2,R]) 都有 (s_b - s_{L+1} eq S)。
使用反证法证明，假定 (forall b in [L+2,R]) 有 (s_b - s_{L+1} = S)，若 (b = R) 则算法已结束，因此 (b in [L+2,R - 1])。
那么由单调性，有 (s_b - s_{L} >= S)，且如果取等号则算法在先前已结束，因此 (s_b - s_L > S)。
根据定义，当 (s_b - s_L > S) 时，右指针将会固定在 (b) 的正确位置，左指针会直接移动到 (L+1)，而右指针不会到达当前的 (R) 的位置，矛盾。
因此在算法运行过程中，若 (a in [0,L],b in[L+1,R]) 中命题成立，则(a in [0,L+1],b in [L+2,R]) 中命题成立。
同理可证明 (a in [0,L],b in [L+1,R+1]) 中命题成立。

那么在算法运行过程中，根据定义移动指针可始终保证命题成立，不会漏掉 (s_b - s_a = S) 的情况。
由于笔者水平问题，证明并不严谨，读者可看大佬原文自行证明。

结语

做题容易，优雅地切题难，切完要证更难啊……
对指点笔者的两位神犇表达膜拜之情。
附上代码包，包含两种方法和数据生成器、检验器和对拍器。
为了实现方便，哈希表使用了 map 容器来代替。
蓝奏云下载