題目描述與示例

題目描述

給定一個含有N個正整數的數組，求出有多少個連續區間（包括單個正整數），它們的和大于等于x。

輸入描述

第一行兩個整數N x (0 < N <= 100000 ,0 <= x <= 10000000)

第二行有N個正整數（每個正整數小于等于100）。

輸出描述

輸出一個整數，表示所求的個數。

示例一

輸入

3 7
3 4 7

輸出

4

說明

3+4
4+7
3+4+7
7

這四組數據都是大于等于7的，所以答案為4

示例二

輸入

10 10000000
1 2 3 4 5 6 7 8 9 10

輸出

0

解題思路

題目要求求連續區間的和，很容易想到使用前綴和的思路來解決。先求出前綴和數組，如對示例一求出[3, 4, 7]的前綴和數組為pre_sum_list = [0, 3, 7, 14]。

由于原數組中每一個元素均為非負整數，故前綴和數組一定是一個非遞減數組。

對于pre_sum_list中的每一個元素pre_sum_list[i]，我們要找到索引j（i < j）。

• j是滿足pre_sum_list[j] - pre_sum_list[i] >= target的第一個索引。
• 此時任意比j大的索引k，都能使得pre_sum_list[k] - pre_sum_list[i] >= target成立，即區間[i,k]是一個符合要求的區間。
• 由于前綴和數組是一個非遞減數組，j的尋找可以很容易地使用二分查找來完成。
• 假設j已經求出，那么對于i而言，一共存在n+1-j個這樣的區間，滿足連續區間和大于等于target。將所有i對應的n+1-j計算并求和，即可以得到答案。

代碼

Python

# 題目：【前綴和】2023B-尋找連續區間
# 分值：100
# 作者：閉著眼睛學數理化
# 算法：前綴和/二分查找
# 代碼有看不懂的地方請直接在群上提問from itertools import accumulaten, target = map(int, input().split())
nums = list(map(int, input().split()))
# 構建前綴和數組
pre_sum_list = [0] + list(accumulate(nums))
# 初始化答案
ans = 0# 只需要遍歷前n個前綴和即可，最后一個前綴和無需考慮
for i in range(n):# 二分查找的目標值bi_target = pre_sum_list[i] + target# 優化：如果發現二分目標值已經超過了數組中所有元素總和# 則必然無法找到以i為起始位置的連續區間，其和大于target# 故直接退出循環即可if bi_target > pre_sum_list[-1]:break# 左閉右開區間# 注意前綴和數組的長度為n+1，故此處right初始化為n+2left, right = i, n+2while left < right:mid = left + (right - left) // 2# 找到第一個大于等于bi_target的數的索引if pre_sum_list[mid] >= bi_target:right = midelse:left = mid + 1# 退出while循環時，j = left = right# 是使得pre_sum_list[j] >= bi_target的第一個索引# 一共有n+1-j個區間，其區間和大于targetans += (n+1-left)print(ans)

Java

import java.util.Scanner;
import java.util.Arrays;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int target = scanner.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++) {nums[i] = scanner.nextInt();}int[] preSum = new int[n + 1];preSum[0] = 0;for (int i = 0; i < n; i++) {preSum[i + 1] = preSum[i] + nums[i];}int ans = 0;for (int i = 0; i < n; i++) {int biTarget = preSum[i] + target;if (biTarget > preSum[n]) {break;}int left = i;int right = n + 2;while (left < right) {int mid = left + (right - left) / 2;if (preSum[mid] >= biTarget) {right = mid;} else {left = mid + 1;}}ans += (n + 1 - left);}System.out.println(ans);}
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int n, target;cin >> n >> target;vector<int> nums(n);for (int i = 0; i < n; i++) {cin >> nums[i];}vector<int> preSum(n + 1, 0);for (int i = 0; i < n; i++) {preSum[i + 1] = preSum[i] + nums[i];}int ans = 0;for (int i = 0; i < n; i++) {int biTarget = preSum[i] + target;if (biTarget > preSum[n]) {break;}int left = i;int right = n + 2;while (left < right) {int mid = left + (right - left) / 2;if (preSum[mid] >= biTarget) {right = mid;} else {left = mid + 1;}}ans += (n + 1 - left);}cout << ans << endl;return 0;
}

時空復雜度

時間復雜度：O(NlogN)。構建前綴和的時間復雜度為O(N)。對于前綴和數組中的每一個元素pre_sum_list[i]，都要進行二分查找，單次二分查找的時間復雜度為O(logN)，一共需要進行N次二分查找。

空間復雜度：O(N)。前綴和數組所占空間。

---

華為OD算法/大廠面試高頻題算法練習沖刺訓練

• 華為OD算法/大廠面試高頻題算法沖刺訓練目前開始常態化報名！目前已服務100+同學成功上岸！

• 課程講師為全網50w+粉絲編程博主@吳師兄學算法 以及小紅書頭部編程博主@閉著眼睛學數理化

• 每期人數維持在20人內，保證能夠最大限度地滿足到每一個同學的需求，達到和1v1同樣的學習效果！

• 60+天陪伴式學習，40+直播課時，300+動畫圖解視頻，300+LeetCode經典題，200+華為OD真題/大廠真題，還有簡歷修改、模擬面試、專屬HR對接將為你解鎖

• 可上全網獨家的歐弟OJ系統練習華子OD、大廠真題

• 可查看鏈接 大廠真題匯總 & OD真題匯總(持續更新)

• 綠色聊天軟件戳 od1336了解更多