【华为OD-E卷 - 数组连续和 100分(python、java、c++、js、c)】
题目
给定一个含有N个正整数的数组, 求出有多少个连续区间(包括单个正整数), 它们的和大于等于x
输入描述
- 第一行两个整数N x(0 < N <= 100000, 0 <= x <= 10000000)
第二行有N个正整数(每个正整数小于等于100)
输出描述
- 输出一个整数,表示所求的个数
备注
- 注意:此题对效率有要求,暴力解法通过率不高,请考虑高效的实现方式
用例
用例一:
输入:
3 7
3 4 7
- 1
- 2
输出:
4
- 1
用例二:
输入:
10 10000
1 2 3 4 5 6 7 8 9 10
- 1
- 2
输出:
0
- 1
python解法
- 解题思路:
- 这道题的目标是计算数组中满足子数组和大于等于给定值 x 的子数组数量。以下是解题的基本思路:
双层循环遍历:
外层循环选择子数组的起始点 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))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
java解法
- 解题思路
- 这道题的目标是计算数组中满足子数组和大于等于给定值 limit 的子数组数量。为了解决问题,我们使用 滑动窗口 技巧来高效计算:
滑动窗口的概念:
通过两个指针 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;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
C++解法
- 解题思路
- 本题的目标是计算数组中满足子数组和大于等于给定值 x 的子数组数量。为了高效解决问题,我们采用 滑动窗口 技术,减少重复计算,提高效率。
滑动窗口的核心思想
使用两个指针 left 和 right 表示滑动窗口的左右边界:
right 指针向右扩展窗口,增加子数组范围。
left 指针向右收缩窗口,减少子数组范围,确保窗口和小于 x。
当窗口内的和 total 大于等于 x 时,说明从 right 到数组末尾的所有子数组都满足条件:
这些子数组以 left 开头,从 right 结束到数组末尾。
子数组数量为 n - right。
在每次确定满足条件的子数组数量后,通过移动 left 指针收缩窗口,同时更新 total。
#include
#include
using namespace std;
/**
* 计算满足条件的子数组数量
*
* @param n 数组的长度
* @param x 子数组和的目标值
* @param arr 数组
* @return 满足条件的子数组数量
*/
long long findIntervals(int n, int x, const vector<int>& arr) {
long long total = 0; // 当前窗口的总和
long long count = 0; // 满足条件的子数组数量
int left = 0; // 滑动窗口的左边界
// 遍历数组,right 代表滑动窗口的右边界
for (int right = 0; right < n; right++) {
total += arr[right]; // 将当前元素加入窗口
// 如果窗口和 >= x,则计算满足条件的子数组数量
while (total >= x) {
count += n - right; // 从 right 到数组末尾的所有子数组都满足条件
total -= arr[left]; // 收缩窗口,移除窗口左边界的元素
left++; // 左边界右移
}
}
return count; // 返回总的满足条件的子数组数量
}
int main() {
int n, x;
// 读取数组长度 n 和目标值 x
cin >> n >> x;
// 读取数组元素
vector<int> arr(n);
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
// 调用函数并输出结果
cout << findIntervals(n, x, arr) << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
C解法
更新中
- 1
JS解法
滑动窗口:
使用两个指针 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; // 返回满足条件的子数组总数量
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
注意:
如果发现代码有用例覆盖不到的情况,欢迎反馈!会在第一时间修正,更新。
解题不易,如对您有帮助,欢迎点赞/收藏
评论记录:
回复评论: