二指针算法

Question

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

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

所以假设我们有一个元素数组 [2, 1, 3, 4, 5] 并且我们的 M 是 12。我们会 return 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 序列不一定意味着总和会增加。

Answer 2

算法有效。它假定数组中的所有值都是正数（或 0），因此对于固定的 l，可以通过 while 循环找到从 l 开始的最佳连续序列，方法是添加正数或零元素，直到当前总和达到之前的最后一个 r M.

到那时你就会知道从 l 开始到 r 之前停止的序列比当前序列小，而在 r 之后停止的序列太大 (>M)。因此，您只需将当前总和与之前的最佳总和进行比较，然后移动到 l 的下一个值。

如果整数可以是负数，那么你是对的，这是行不通的。

二指针算法

The two pointer algorithm

algorithm

greedy