问题
给定一个数组 arr,该数组无序,但每个值均为正数,再给定一个正数 k。求 arr 的所有子数组中所有元素相加和为 k 的最长子数组长度。 例如,arr=[1,2,1,1,1],k=3。累加和为 3 的最长子数组为[1,1,1],所以结果返回 3。
时间复杂度 O(N),额外空间复杂度 O(1)
思路
未排序正数数组中累加和为给定值的最长子数组长度问题,仍是双指针
系列的问题。但与之前不同的是,本题左右工作指针从同一侧出发
。L和R都被初始化为0,指向arr[0]元素。
左右工作指针的移动策略
sum < k 时,R++;sum >= k 时,L++;
R到达数组末尾时,循环结束跳出;
我们的目标是求最长子数组的长度,根据贪心的思想,当L到达目标子数组的左端
,sum < k(目标累加和)时,我们的L指针固定不动,R指针应该尽可能的向右移动,直到到达目标子数组的最右端
。sum = k时,记录子数组 len = R - L
;
R再继续右移,那么sum > k ,我们的L指针要向左移动一位 L++,同样的 原理求子数组的左端为L++的最大长度
。R到达数组最右端,不管sum值如何,L移动,len只会不断减少
。故R到达最 右端时,直接结束跳出循环
通过上面的说明,可以看出左右工作指针的移动策略,可以保证我们不会错过最长子数组长度的记录,并且遍历到所有累加和小于k的子数组
。
核心代码
int getMaxLength(int *arr, int k)
{
if (arr == NULL || length == 0 || k <= 0)
{
return 0;
}
//初始化
int len = 1;
int sum = arr[0];
int L = 0;
int R = 0;
while (R < length)
{
//sum >= k, sum先减,再移动L
if (sum == k)
{
len = max(len, R - L + 1);
sum -= arr[L];
L++;
}
else if (sum > k)
{
sum -= arr[L];
L++;
}
//sum < k, 先移动R,sum再加
else
{
R++;
//检查是否越界
if (R == length) {
break;
}
sum += arr[R];
}
}
return len;
}
注意
:sum值为L到R的子数组累加和,子数组为闭区间,sum值包含l,r位置的元素值