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

news/2025/1/18 20:11:57/

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/news/1564229.html

相关文章

Centos 宝塔安装

Centos 宝塔安装

yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh 安装成功界面 宝塔说明文档 https://www.bt.cn/admin/servers#wcu 或者可以注册宝塔账号 1 快速部署 安装docker 之后 2 需要在usr/bin下下载do…
阅读更多...
5 分钟复刻你的声音，一键实现 GPT-Sovits 模型部署

5 分钟复刻你的声音，一键实现 GPT-Sovits 模型部署

想象一下&#xff0c;只需简单几步操作&#xff0c;就能生成逼真的语音效果&#xff0c;无论是为客户服务还是为游戏角色配音&#xff0c;都能轻松实现。GPT-Sovits 模型&#xff0c;其高效的语音生成能力为实现自然、流畅的语音交互提供了强有力的技术支持。本文将详细介绍如何…
阅读更多...
C++实现设计模式---迭代器模式 (Iterator)

C++实现设计模式---迭代器模式 (Iterator)

迭代器模式 (Iterator) 迭代器模式 是一种行为型设计模式&#xff0c;它提供了一种方法&#xff0c;顺序访问一个聚合对象中的各个元素&#xff0c;而又不需要暴露该对象的内部表示。 意图 提供一种方法&#xff0c;可以顺序访问一个容器对象中的元素&#xff0c;而无需暴露其…
阅读更多...
MyBatis缓存原理及插件实现

MyBatis缓存原理及插件实现

目录 MyBatis缓存原理 缓存的工作机制 一级缓存&#xff1a; 二级缓存&#xff1a; MyBatis插件实现 MyBatis缓存原理 缓存的工作机制 如果会话查询了一条数据&#xff0c;此数据会存入一级缓存&#xff1b;若会话被关闭或提交&#xff0c;则&#xff0c;其数据转存入二级缓…
阅读更多...
Nacos: 一个动态服务发现与配置管理平台

Nacos: 一个动态服务发现与配置管理平台

Nacos: 一个动态服务发现与配置管理平台 引言 在微服务架构日益普及的今天&#xff0c;服务之间的调用和配置管理变得越来越复杂。为了简化这一过程并提高开发效率&#xff0c;阿里巴巴推出了Nacos——一个易于使用的动态服务发现、配置管理和服务管理平台。 Nacos是什么&am…
阅读更多...
C#图表性能的巅峰之选：LightningChart®.NET

C#图表性能的巅峰之选：LightningChart®.NET

C#图表性能的巅峰之选&#xff1a;LightningChart.NET 引言 在现代数据可视化中&#xff0c;性能是选择图表控件的关键因素。无论是实时数据监控、海量数据分析还是复杂 3D 可视化&#xff0c;LightningChart.NET 都以其卓越的性能成为市场上的佼佼者。 本文将深入探讨 Ligh…
阅读更多...
渗透笔记1

渗透笔记1

第一天 工具&#xff1a;cs cobalt strike 4.9 / msf kali &#xff08;自带 Ubuntu&#xff09; cs cobalt strike 4.9&#xff1a;server-client server部署在云服务器上&#xff0c;client分别在各地&#xff0c;与server相连接&#xff1b;连接上后就可以共享上线主机。…
阅读更多...
IM聊天学习资源

IM聊天学习资源

文章目录 参考链接使用前端界面简单效果消息窗口平滑滚动至底部vue使用watch监听vuex中的变量变化 websocket握手认证ChatKeyCheckHandlerNettyChatServerNettyChatInitializer 参考链接 zzhua/netty-chat-web - 包括前后端 vue.js实现带表情评论功能前后端实现&#xff08;仿…
阅读更多...
最新文章

Copyright @ 2022~2023