首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐

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

  • 25-03-07 19:22
  • 2288
  • 9912
blog.csdn.net

【华为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解法

  • 解题思路

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

滑动窗口:

使用两个指针 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

注意:

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

注:本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/145185130"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

101
推荐
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2025 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top