algorithm - 二指针算法

Question

我试图理解双指针算法方法，所以我一直在阅读 this article

那么问题来了。假设我们有一个包含 N 个元素的数组。我们想在该数组中找到总和小于或等于 M 的最大连续元素序列。我们必须返回元素序列总和的值。

假设我们有一个元素数组 [2, 1, 3, 4, 5] 并且我们的 M 是 12。我们将返回 12，因为 3、4 和 5 的总和为 12。这是文章中的方法

• 我们介绍两个指针 l , r表示我们连续子数组的 startIndex 和 endIndex，它们都位于数组的顶端。
• 我们现在开始扩展右指针 r提供sum[l,r] <= M曾经，我们到了这样的地步，别无选择，只能也移动左指针并开始减少总和直到我们到达了可以扩展右指针的情况再次。
• 当我们到达需要向左移动的位置时指针，我们不断更新我们迄今为止取得的最大总和。

这是 C++ 代码。

#include <bits/stdc++.h>
#define lli long long
#define MAX 1000005

using namespace std;

lli A[MAX];

int main()
{
    int n;
    lli sum = 0;     
    cin >> n;

    for ( int i = 0; i < n; i++ ) cin >> A[i];

    int l = 0, r = 0;
    lli ans = 0;

    while ( l < n ) {
       while ( r < n && sum + A[r] <= M ) {
           sum += A[r];
           r++;
       }
       ans = max(ans, sum);
       sum -= A[l];
       l++;
    }

    cout << ans << endl;
    return 0;
}

但我不明白为什么这种方法有效。我们没有考虑所有可能的连续子序列。一旦超过总和，我们就记下当前的子序列长度，比较它是否比前一个大，然后简单地增加 l。并重复这个过程。

我不明白这是如何产生正确结果的。

Answer 1

该方法之所以有效，是因为对于每个 r 指针，当前 l 实际上代表最左边的一个，因此总和仍低于阈值。

因此没有必要查看以 r 指针结尾的所有其他序列。

但是，如果允许负数，则该方法无效。在那种情况下，更长的 l - r 序列不一定意味着总和会增加。