[GoogleInterview]连续子序列问题
本文最后更新于 59 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

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

前言

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

题面

GoogleInterviewProblem.png

给定一个无序数组 $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(n\log 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 \neq S$。

  1. 初始时,不考虑空数组的情况,从 $L = 0,R = 1$ 开始,若成立则算法退出,否则命题成立。
  2. 假定 $\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} \neq 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]$ 中命题成立。

  1. 同理可证明 $a \in [0,L],b \in [L+1,R+1]$ 中命题成立。

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

结语

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

本文标题:[GoogleInterview]连续子序列问题
本文作者:Clouder
本文链接: https://www.codein.icu/gci-subarray/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇