【华为OD-E卷 - 数组连续和 100分（python、java、c++、js、c）】

devtools/2025/1/18 8:51:02/

pythonjavacjsc_0">【华为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
输出：
4
用例二：
输入：
10 10000
1 2 3 4 5 6 7 8 9 10
输出：
0

python_53">python解法

  • 解题思路：
  • 这道题的目标是计算数组中满足子数组和大于等于给定值 x 的子数组数量。以下是解题的基本思路：

双层循环遍历：

外层循环选择子数组的起始点 i。
内层循环选择子数组的结束点 j，计算从 i 到 j 的子数组和 total。
提前终止内层循环：

一旦找到一个子数组的和 total 大于等于 x，就可以确定从 j 开始到数组末尾的所有子数组都满足条件。原因是这些子数组都以 i 为起点，而子数组越长，和只会更大。
优化：

当找到第一个满足条件的 j 后，直接计算满足条件的子数组数量 N - j，并结束内层循环

python">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 和目标值 xN, x = map(int, input_lines[0].split())# 解析第二行，得到数组 numsnums = list(map(int, input_lines[1].split()))# 调用函数并输出结果print(count_subarrays(N, x, nums))

java_107">java解法

  • 解题思路
  • 这道题的目标是计算数组中满足子数组和大于等于给定值 limit 的子数组数量。为了解决问题，我们使用 滑动窗口 技巧来高效计算：

滑动窗口的概念：

通过两个指针 start 和 end 来定义一个窗口，窗口表示当前子数组的范围。
指针 end 用于扩展窗口，增加子数组的范围。
指针 start 用于收缩窗口，排除不必要的元素，保证子数组和小于 limit。
操作逻辑：

每次将 values[end] 加入当前窗口的和 sum。
如果 sum 大于等于 limit，说明从 start 到 end 的子数组满足条件，而对于当前 end，从 start 到数组末尾的子数组也都满足条件，可以直接计算这些子数组的数量：num - end。
然后收缩窗口，即移动 start 指针并从 sum 中减去 values[start]。
优化：

通过滑动窗口，只需遍历每个元素一次（每个元素最多被加入和移除一次），时间复杂度为
𝑂
(
𝑛
)
O(n)，比使用双层循环的暴力方法更高效

java">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];// 如果当前窗口的和 >= limitwhile (sum >= limit) {// 从当前起点到数组末尾的子数组都满足条件total += num - end;// 缩小窗口，移除窗口的起始值sum -= values[start++];}// 扩展窗口的终点end++;}// 返回总的满足条件的子数组数量return total;}
}

C++解法

  • 解题思路
  • 本题的目标是计算数组中满足子数组和大于等于给定值 x 的子数组数量。为了高效解决问题，我们采用 滑动窗口 技术，减少重复计算，提高效率。

滑动窗口的核心思想
使用两个指针 left 和 right 表示滑动窗口的左右边界：

right 指针向右扩展窗口，增加子数组范围。
left 指针向右收缩窗口，减少子数组范围，确保窗口和小于 x。
当窗口内的和 total 大于等于 x 时，说明从 right 到数组末尾的所有子数组都满足条件：

这些子数组以 left 开头，从 right 结束到数组末尾。
子数组数量为 n - right。
在每次确定满足条件的子数组数量后，通过移动 left 指针收缩窗口，同时更新 total。

#include <iostream>
#include <vector>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 和目标值 xcin >> n >> x;// 读取数组元素vector<int> arr(n);for (int i = 0; i < n; ++i) {cin >> arr[i];}// 调用函数并输出结果cout << findIntervals(n, x, arr) << endl;return 0;
}

C解法

  • 解题思路

更新中

JS解法

  • 解题思路

  • 这道题要求我们计算数组中满足子数组和大于等于给定值 x 的子数组数量。为了高效完成此任务，采用 滑动窗口 技术：

滑动窗口：

使用两个指针 left 和 right 表示滑动窗口的左右边界。
right 用于扩展窗口范围，加入当前元素，增加窗口和。
当窗口和大于等于 x 时，收缩窗口，移除左边界元素，减小窗口和。
满足条件时直接计算数量：

如果当前窗口和 total 大于等于 x，说明从 right 到数组末尾的所有子数组都满足条件。可以直接通过 n - right 计算这些子数组的数量。

javascript">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 和目标值 xconst 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; // 返回满足条件的子数组总数量
}

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏


http://www.ppmy.cn/devtools/151519.html

相关文章

ASP.NET Core - 依赖注入(四)

ASP.NET Core - 依赖注入(四)

ASP.NET Core - 依赖注入&#xff08;四&#xff09; 4. ASP.NET Core默认服务5. 依赖注入配置变形 4. ASP.NET Core默认服务 之前讲了中间件&#xff0c;实际上一个中间件要正常进行工作&#xff0c;通常需要许多的服务配合进行&#xff0c;而中间件中的服务自然也是通过 Ioc…
阅读更多...
某国际大型超市电商销售数据分析和可视化

某国际大型超市电商销售数据分析和可视化

完整源码项目包获取→点击文章末尾名片&#xff01; 本作品将从人、货、场三个维度&#xff0c;即客户维度、产品维度、区域维度&#xff08;补充时间维度与其他维度&#xff09;对某国际大型超市的销售情况进行数据分析和可视化报告展示&#xff0c;从而为该超市在弄清用户消费…
阅读更多...
【蓝桥杯选拔赛真题63】C++奇数 第十四届蓝桥杯青少年创意编程大赛 算法思维 C++编程选拔赛真题解

【蓝桥杯选拔赛真题63】C++奇数 第十四届蓝桥杯青少年创意编程大赛 算法思维 C++编程选拔赛真题解

目录 C++奇数 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、运行结果 五、考点分析 七、推荐资料 C++奇数 第十四届蓝桥杯青少年创意编程大赛C++选拔赛真题 一、题目要求 1、编程实现 给定两个正整数N和M(10≤N<M≤10000)，请找出N到M…
阅读更多...
minio https配置

minio https配置

minio启动时候指定数据目录,配置文件&#xff0c;密钥文件目录&#xff0c;环境文件 1.创建minio用户,专门用于服务启动的 groupadd -r minio-user useradd -M -r -g minio-user minio-user 2.在当前用户目录下创建minio目录&#xff0c;存储minio相关文件 mkdir minio 在mini…
阅读更多...
微软震撼发布：Phi-4语言模型登陆Hugging Face

微软震撼发布：Phi-4语言模型登陆Hugging Face

近日&#xff0c;微软公司在Hugging Face平台上正式发布了其最新的语言模型Phi-4&#xff0c;这一发布标志着人工智能技术的又一重要进步。Phi-4模型以其140亿参数的高效配置&#xff0c;在复杂推理任务中表现出色&#xff0c;特别是在数学领域&#xff0c;更是展现出了卓越的能…
阅读更多...
安装Docker流程

安装Docker流程

1.卸载旧版 首先如果系统中已经存在旧的Docker&#xff0c;则先卸载&#xff1a; yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-engine 2.配置Docker的yum库 首先要安装一个…
阅读更多...
青少年编程与数学 02-007 PostgreSQL数据库应用 03课题、安装pgAdmin

青少年编程与数学 02-007 PostgreSQL数据库应用 03课题、安装pgAdmin

青少年编程与数学 02-007 PostgreSQL数据库应用 03课题、安装pgAdmin 一、pgAdmin二、安装Windows系统安装pgAdminLinux系统安装pgAdmin 三、语言四、配置1. 设置服务器连接2. 配置pgAdmin界面3. 配置SQL编辑器4. 配置浏览器树5. 安全性配置6. 导入和导出数据 课题摘要:本课题介…
阅读更多...
无人机航拍价格 航拍价格

无人机航拍价格 航拍价格

无人机航拍的价格因多种因素而异&#xff0c;包括拍摄的复杂性、所需设备、后期处理、拍摄地点、专业水平等。以下是一些常见的价格范围和影响价格的因素&#xff1a; 1. 拍摄类型和复杂性 基础航拍&#xff1a;简单的风景拍摄或小型活动拍摄&#xff0c;价格通常在500-1500元…
阅读更多...
最新文章

Copyright @ 2022~2023