最长子数组长度

问题

给定一个数组 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位置的元素值