题目描述

给定一个含有 $N$ 个正整数的数组，求出有多少个连续子数组（包括单个正整数），其元素之和满足 $\sum \ge x$。

输入描述
第一行为两个整数 $N$, $x$。其中 $0<N\le 10^5$, $0\le x\le 10^7$
第二行包含 $N$ 个正整数（每个数 $\le 100$）

输出描述
输出满足条件的连续子数组个数

输入输出示例

示例 1:
输入：

3 7
3 4 7

输出：

4

解释：
满足条件的子数组为：

• $[3,4]$ (和为 $7$)
• $[3,4,7]$ (和为 $14$)
• $[4,7]$ (和为 $11$)
• $[7]$ (和为 $7$)

解题思路

1. 问题分析：

   • 需要统计所有满足 ${\sum }_{i=l}^r{a}_i\ge x$ 的区间 $[l,r]$ 的个数
   • 暴力解法时间复杂度为 $O(N^2)$，无法通过大规模数据

2. 优化思路：

   • 利用滑动窗口（双指针）技术
   • 维护窗口和 $sum$，当 $sum\ge x$ 时统计有效区间数

3. 算法流程：

   1. 初始化指针 $left=0$，窗口和 $sum=0$，计数器 $count=0$
   2. 遍历数组，右指针 $right$ 从 $0$ 到 $N-1$：
      • 将 $a[right]$ 加入 $sum$
      • 当 $sum\ge x$ 时：
        • 所有以 $right$ 结尾的子数组 $[l,right]$（$l\le left$）都满足条件
        • 增加计数 $count\leftarrow count+(N-right)$
        • 移动左指针缩小窗口：$sum\leftarrow sum-a[left],left\leftarrow left+1$

代码实现

Java

import java.util.Scanner;// 博主亲测版
public class 寻找连续区间 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int len = scanner.nextInt();int target = scanner.nextInt();int[] arr = new int[len];for (int i = 0; i < len; i++) {arr[i] = scanner.nextInt();}int sum = 0;int tempSum;int count = 0;for (int right = 0; right < len; right++) {sum += arr[right];tempSum = sum;for (int left = 0; left <= right; left++) {if (tempSum >= target) {tempSum -= arr[left];count++;}}}System.out.println(count);}
}

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int x = sc.nextInt();int[] a = new int[N];for (int i = 0; i < N; i++) a[i] = sc.nextInt();int count = 0, left = 0, sum = 0;for (int right = 0; right < N; right++) {sum += a[right];while (sum >= x) {count += N - right;sum -= a[left++];}}System.out.println(count);}
}

Python

n, x = map(int, input().split())
a = list(map(int, input().split()))count = left = current_sum = 0
for right in range(n):current_sum += a[right]while current_sum >= x:count += n - rightcurrent_sum -= a[left]left += 1print(count)

C++

#include <iostream>
#include <vector>
using namespace std;int main() {int N, x;cin >> N >> x;vector<int> a(N);for (int i = 0; i < N; i++) cin >> a[i];int count = 0, left = 0, sum = 0;for (int right = 0; right < N; right++) {sum += a[right];while (sum >= x) {count += N - right;sum -= a[left++];}}cout << count << endl;return 0;
}

JavaScript

const readline = require('readline');
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let input = [];
rl.on('line', line => {input.push(line);
}).on('close', () => {const [N, x] = input[0].split(' ').map(Number);const a = input[1].split(' ').map(Number);let count = 0, left = 0, sum = 0;for (let right = 0; right < N; right++) {sum += a[right];while (sum >= x) {count += N - right;sum -= a[left++];}}console.log(count);
});

复杂度分析

• 时间复杂度：$O(N)$
  每个元素最多被访问两次（右指针和左指针各一次）
• 空间复杂度：$O(1)$
  仅使用常数个额外变量

测试用例

测试用例 1
输入：

5 10
1 2 3 4 5

输出：

9

解释：
满足条件的子数组：
$[1,2,3,4]$, $[1,2,3,4,5]$,
$[2,3,4]$, $[2,3,4,5]$,
$[3,4,5]$, $[4,5]$, $[5]$

测试用例 2
输入：

1 100
50

输出：

0

测试用例 3
输入：

4 5
5 1 1 5

输出：

6

问题总结

1. 关键点：

   • 利用滑动窗口维护当前子数组和
   • 当和满足条件时，快速计算以当前右指针结尾的有效子数组数

2. 算法选择：

   • 滑动窗口适用于正数数组的区间和问题
   • 保证线性时间复杂度，适合大规模数据

3. 扩展思考：

   • 如果包含负数，需要改用前缀和+二分查找
   • 类似问题：求满足 $\sum \le x$ 的子数组数