求数组中和小于B的子数组数量：优化解法错误排查及方案问询

你的滑动窗口代码存在两个关键错误：

• 当窗口和currentSum >= B时，仅移动一次左指针start无法确保窗口和满足<B的条件——因为数组元素都是非负整数，减去A[start]后可能仍不满足要求，需要循环移动左指针直到窗口和小于B。
• 无论窗口和是否符合条件都直接累加子数组数量，会把不符合要求的子数组也统计进去，只有当窗口和严格小于B时，才能计算以当前右指针结尾的有效子数组数量。

正确实现代码 #

const countSubarrays = (A, B) => {
    let start = 0;
    let ans = 0;
    let currentSum = 0;
    const n = A.length;

    for (let end = 0; end < n; end++) {
        currentSum += A[end];
        // 循环调整左指针，确保窗口和小于B，同时避免左指针越界
        while (currentSum >= B && start <= end) {
            currentSum -= A[start];
            start++;
        }
        // 统计以当前end结尾的所有有效子数组数量
        ans += end - start + 1;
    }

    return ans;
}

// 测试验证
const A = [2, 5, 6];
const B = 10;
const result = countSubarrays(A, B);
console.log('result: ', result); // 输出4，与暴力解法结果一致

逻辑说明 #

1. 遍历右指针end，将当前元素加入窗口总和currentSum。
2. 用while循环左移start：只要窗口总和大于等于B且左指针不超过右指针，就不断从总和中减去左指针元素并移动左指针，直到窗口总和严格小于B。
3. 此时，以end结尾的有效子数组，是从start到end的所有后缀子数组，数量为end - start + 1（例如窗口范围是[start, end]，有效子数组为[A[end]]、[A[end-1], A[end]]...[A[start], ..., A[end]]）。

内容的提问来源于stack exchange，提问作者Ashy Ashcsi