子阵求和

Question

我最近遇到了一个两个指针的子数组求和问题的解决方案，我不太确定算法的正确性。子数组求和问题包括寻找一个和等于某个目标值的子数组。我见过使用哈希表解决这个问题的方法，但我质疑另一个解决方案的正确性。让我给你们一个算法的例子。

假设有一个数组[1,3,2,5,1,1,2,3]，目标值x=8。

使用指示子数组开始和结束的左指针和右指针。在每一步中，左指针向前移动一步，右指针向前移动，只要子数组和至多为x。以上数组的算法将以这种方式进行。

[1,3,2,5,1,1,2,3]
l    r

[1,3,2,5,1,1,2,3] ##The right pointer doesn't move because the next element would make the sum larger than x
   l r

[1,3,2,5,1,1,2,3]
     l   r

Answer 1

设LEN(i)是从索引i开始，和至多为X的最长子数组的长度

如果有一个子数组的和X从索引i开始，那么LEN(i)将是这样一个子数组的长度（可能有多个数组尾随0）。因为数组中只有正整数，所以从i开始的所有较长数组的和都较大，而所有较短的数组的和都相等或较小。

所以我们所需要做的就是找到每个索引的LEN(i)和相应子数组的和。如果其中一个和是X，那么你就有了答案。