给定一个含有N个正整数的数组, 求出有多少个连续区间（包括单个正整数）, 它们的和大于等于x
第二行有N个正整数（每个正整数小于等于100)
3 7
3 4 7
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">4
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">10 10000
1 2 3 4 5 6 7 8 9 10
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">0
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">双层循环遍历：
外层循环选择子数组的起始点 i。
内层循环选择子数组的结束点 j，计算从 i 到 j 的子数组和 total。
提前终止内层循环：
一旦找到一个子数组的和 total 大于等于 x，就可以确定从 j 开始到数组末尾的所有子数组都满足条件。原因是这些子数组都以 i 为起点，而子数组越长，和只会更大。
优化：
当找到第一个满足条件的 j 后，直接计算满足条件的子数组数量 N - j，并结束内层循环
def count_subarrays(N, x, nums):
# 初始化满足条件的子数组计数器
count = 0
# 遍历数组的每个起始点
for i in range(N):
# 初始化当前子数组的和
total = 0
# 遍历从起始点到末尾的所有子数组
for j in range(i, N):
total += nums[j] # 累加当前子数组的和
# 如果当前子数组的和 >= x，计算满足条件的子数组数量
if total >= x:
count += N - j # 从 j 开始到数组末尾的子数组都满足条件
break # 结束内层循环，跳到下一个起始点
return count # 返回满足条件的子数组总数
if __name__ == "__main__":
import sys
# 读取标准输入的多行数据
input_lines = sys.stdin.read().strip().splitlines()
# 解析第一行，得到数组长度 N 和目标值 x
N, x = map(int, input_lines[0].split())
# 解析第二行，得到数组 nums
nums = list(map(int, input_lines[1].split()))
# 调用函数并输出结果
print(count_subarrays(N, x, nums))
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">滑动窗口的概念：
通过两个指针 start 和 end 来定义一个窗口，窗口表示当前子数组的范围。
指针 end 用于扩展窗口，增加子数组的范围。
指针 start 用于收缩窗口，排除不必要的元素，保证子数组和小于 limit。
操作逻辑：
每次将 values[end] 加入当前窗口的和 sum。
如果 sum 大于等于 limit，说明从 start 到 end 的子数组满足条件，而对于当前 end，从 start 到数组末尾的子数组也都满足条件，可以直接计算这些子数组的数量：num - end。
然后收缩窗口，即移动 start 指针并从 sum 中减去 values[start]。
优化：
通过滑动窗口，只需遍历每个元素一次（每个元素最多被加入和移除一次），时间复杂度为
𝑂
(
𝑛
)
O(n)，比使用双层循环的暴力方法更高效
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 读取数组的大小和目标值
int num = in.nextInt();
int limit = in.nextInt();
// 初始化数组并读取值
int[] values = new int[num];
for (int i = 0; i < num; i++) {
values[i] = in.nextInt();
}
// 调用方法计算满足条件的子数组数量并输出结果
System.out.println(findSubarrays(num, limit, values));
}
/**
* 计算满足条件的子数组数量
* @param num 数组的长度
* @param limit 子数组和的目标值
* @param values 数组
* @return 满足条件的子数组数量
*/
public static long findSubarrays(int num, int limit, int[] values) {
// 定义窗口的起点和终点
int start = 0, end = 0;
// 当前窗口的和
long sum = 0;
// 满足条件的子数组数量
long total = 0;
// 遍历数组，扩展窗口
while (end < num) {
// 将当前元素加入窗口
sum += values[end];
// 如果当前窗口的和 >= limit
while (sum >= limit) {
// 从当前起点到数组末尾的子数组都满足条件
total += num - end;
// 缩小窗口，移除窗口的起始值
sum -= values[start++];
}
// 扩展窗口的终点
end++;
}
// 返回总的满足条件的子数组数量
return total;
}
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">滑动窗口的核心思想
使用两个指针 left 和 right 表示滑动窗口的左右边界：
right 指针向右扩展窗口，增加子数组范围。
left 指针向右收缩窗口，减少子数组范围，确保窗口和小于 x。
当窗口内的和 total 大于等于 x 时，说明从 right 到数组末尾的所有子数组都满足条件：
这些子数组以 left 开头，从 right 结束到数组末尾。
子数组数量为 n - right。
在每次确定满足条件的子数组数量后，通过移动 left 指针收缩窗口，同时更新 total。
#include 更新中
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">滑动窗口：
使用两个指针 left 和 right 表示滑动窗口的左右边界。
right 用于扩展窗口范围，加入当前元素，增加窗口和。
当窗口和大于等于 x 时，收缩窗口，移除左边界元素，减小窗口和。
满足条件时直接计算数量：
如果当前窗口和 total 大于等于 x，说明从 right 到数组末尾的所有子数组都满足条件。可以直接通过 n - right 计算这些子数组的数量。
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
rl.on("line", (line) => {
// 初始化输入行存储数组
if (!this.lines) this.lines = [];
this.lines.push(line);
// 当输入达到两行时，处理输入数据
if (this.lines.length === 2) {
const [n, x] = this.lines[0].split(" ").map(Number); // 解析第一行，获取数组长度 n 和目标值 x
const arr = this.lines[1].split(" ").map(Number); // 解析第二行，获取数组元素
console.log(findIntervals(n, x, arr)); // 调用核心函数并打印结果
this.lines = []; // 清空存储的输入数据
}
});
/**
* 滑动窗口算法计算满足条件的子数组数量
*
* @param {number} n 数组长度
* @param {number} x 目标值
* @param {number[]} arr 数组
* @return {number} 满足条件的子数组数量
*/
function findIntervals(n, x, arr) {
let total = 0; // 当前窗口的和
let count = 0; // 满足条件的子数组数量
let left = 0; // 滑动窗口的左边界
// 遍历数组，right 表示滑动窗口的右边界
for (let right = 0; right < n; right++) {
total += arr[right]; // 将当前元素加入窗口
// 当窗口和 >= x 时，计算满足条件的子数组数量
while (total >= x) {
count += n - right; // 从 right 到数组末尾的所有子数组都满足条件
total -= arr[left++]; // 收缩窗口，移除窗口左边界的元素
}
}
return count; // 返回满足条件的子数组总数量
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：