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

【华为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"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！