未排序正数数组中累加和为给定值的最长子数组的长度

未排序正数数组中累加和为给定值的最长子数组的长度

题目描述

给定一个数组arr，该数组无序，但每个值均为正数，再给定一个正数k。求arr的所有子数组中所有元素相加和为k的最长子数组的长度

例如，arr = [1, 2, 1, 1, 1], k = 3

累加和为3的最长子数组为[1, 1, 1]，所以结果返回3

[要求]

时间复杂度为$O(n)$，空间复杂度为$O(1)$

输入描述：

第一行两个整数N, k。N表示数组长度，k的定义已在题目描述中给出
第二行N个整数表示数组内的数

输出描述：

输出一个整数表示答案

示例1

输入

5 3
1 2 1 1 1

输出

3

备注：

$1\le N\le 10^5$
$1\le k\le 10^9$

$1\le ar{r}_i\le 100$

题解：

双指针。使用 left 和 right 两个指针表示子数组的左右位置，sum 表示子数组的和。分以下几种情况：

• sum == k，更新最大长度，sum -= arr[left]，左指针右移（left++）；
• sum < k，右指针右移（right++），sum += arr[right]；
• sum > k，sum -= arr[left]，左指针右移（left++）。

代码：

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100000;

int n, k;
int a[N];

int main(void) {
    scanf("%d%d", &n, &k);
    for ( int i = 0; i < n; ++i ) scanf("%d", a + i);
    int l = 0, r = 0;
    int sum = a[0], len = 0;
    while ( r < n ) {
        if ( sum > k ) sum -= a[ l++ ];
        else if ( sum < k ) {
            if ( r == n - 1 ) break;
            sum += a[ ++r ];
        }
        else {
            len = max( len, r - l + 1 );
            sum -= a[ l++ ];
        }
    }
    return 0 * printf("%d\n", len);
}