区间和的个数

题目链接

区间和的个数

题目描述

注意点

  • 求数组中,值位于范围 [lower, upper] (包含 lower 和 upper)之内的 区间和的个数
  • -2^31 <= nums[i] <= 2^31 - 1
  • -10^5 <= lower <= upper <= 10^5

解答思路

  • 参照题解使用归并排序解决本题,思路为:
    • 假设数组分为了两个升序排序的部分,从数组arr1从左往右取一个元素i,在确定i之后,从数组arr2找到一个区间[idxR1, idxR2]满足arr2区间内的所有值减去arr1[i]的值都处于[lower, upper]内,[idxR1, idxR2]有多少个元素说明有多少个满足题意的区间和,移动元素i重复上述过程也就找到了本次归并的区间和的个数
    • 需要注意的是,计算区间和时元素必须是相连的,所以不能直接对原数组调换顺序,而应该先计算每个位置的前缀和,然后对前缀和进行归并排序,这样arr2的某个前缀和减去arr1的某个前缀和实际上是某一段连续元素的区间和
    • 需要注意的是,为了方便考虑从第一个元素开始的连续数组的区间和,需要将前缀和数组arr的长度设置为n + 1,arr[0] = 0

代码

class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        int n = nums.length;
        long sum = 0;
        // arr[0]方便计算统计仅取右侧部分元素区间和
        long[] arr = new long[n + 1];
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            arr[i + 1] = sum;
        }
        return countMergeRangeSum(arr, lower, upper, 0, n);
    }

    public int countMergeRangeSum(long[] arr, int lower, int upper, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int res = 0;
        int mid = left + ((right - left + 1) >> 1);
        // 左归并并统计左侧区间和个数
        res += countMergeRangeSum(arr, lower, upper, left, mid - 1);
        // 右归并并统计右侧区间和个数
        res += countMergeRangeSum(arr, lower, upper, mid, right);
        int idxR1 = mid, idxR2 = mid;
        // 随着i向右移动,arr[i]增大,则右侧区间和减去arr[i]要满足[lower, upper]条件,idxR1和idxR2的区间也必定向右移动
        for (int i = left; i < mid; i++) {
            while (idxR1 <= right && arr[idxR1] - arr[i] < lower) {
                idxR1++;
            }
            while (idxR2 <= right && arr[idxR2] - arr[i] <= upper) {
                idxR2++;
            }
            res += idxR2 - idxR1;
        }
        // 归并排序
        long[] newArr = mergeArr(arr, left, right, mid);
        for (int i = 0; i < newArr.length; i++) {
            arr[i + left] = newArr[i];
        }
        return res;
    }

    public long[] mergeArr(long[] arr, int left, int right, int mid) {
        long[] newArr = new long[right - left + 1];
        int idx = 0, l = left, r = mid;
        while (l <= mid - 1 || r <= right) {
            if (l > mid - 1) {
                newArr[idx++] = arr[r++];
                continue;
            }
            if (r > right) {
                newArr[idx++] = arr[l++];
                continue;
            }
            if (arr[l] < arr[r]) {
                newArr[idx++] = arr[l++];
            } else {
                newArr[idx++] = arr[r++];
            }
        }
        return newArr;
    }
}

关键点

  • 归并排序的思想
  • 初始化前缀和的数组后,数组内的任意两个元素相减都是原数组任意一段连续数组的区间和
  • 注意考虑包含第一个元素的区间和的情况

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/875599.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

游戏开发引擎___unity位置信息和unlit shader(无光照着色器)的使用,以桌子的渲染为例

unity是左手坐标系 1.位置信息 1.1 代码 using System.Collections; using System.Collections.Generic; using UnityEngine;public class positionTest : MonoBehaviour {public Camera Camera;private void OnGUI(){//世界坐标系&#xff0c;GUI里的标签GUI.Label(new Rec…

Linux 挂载磁盘与开机自动挂载操作指南

Linux 挂载磁盘与开机自动挂载操作指南 文章目录 Linux 挂载磁盘与开机自动挂载操作指南一 挂载磁盘1 查看硬盘信息2 新增数据盘执行分区3 新建分区4 创建一个主分区5 分区编号6 初始磁柱编号7 截止磁柱编号8 查看新建分区信息9 分区结果写入10 新分区同步操作系统11 设置新分区…

9.12 TFTP通信

客户端设计&#xff08;仅供参考&#xff09;&#xff1a; 下载本质&#xff1a;读取服务器发送的数据包&#xff0c;写入到本地文件 上传本质&#xff1a;读取本地文件内容&#xff0c;发送给服务器。 1、建立菜单选项&#xff0c;上传和下载。 2、上传功能函数&#xff1a; …

【程序分享】Warren Cowley Parameters 程序:表征短程有序的化学基序

分享一个 Warren Cowley Parameters 程序&#xff1a;表征短程有序的化学基序。 感谢论文的原作者&#xff01; 主要内容 “晶体材料的化学成分具有原子尺度的波动&#xff0c;可调节各种中尺度特性。建立此类材料的化学-微结构关系需要对这些化学波动进行适当的表征。然而&…

2024网安周今日开幕,亚信安全亮相30城

2024年国家网络安全宣传周今天在广州拉开帷幕。今年网安周继续以“网络安全为人民&#xff0c;网络安全靠人民”为主题。2024年国家网络安全宣传周涵盖了1场开幕式、1场高峰论坛、5个重要活动、15场分论坛/座谈会/闭门会、6个主题日活动和网络安全“六进”活动。亚信安全出席20…

yolov8-obb中存在的一个bug

yolov8支持OBB目标检测,且能提供较好的性能。 但是最近在使用yolov8-obb的过程中,发现yolov8-obb存在一个bug。即训练数据如果包含不带旋转角度的水平目标时,训练出的模型,经常会输出垂直的检测框,需要旋转90度以后才能得到最终结果。把yolov8-obb相关的源码阅读一遍才发…

【数学建模】2024数学建模国赛经验分享

文章目录 一、关于我二、我的数模历程三、经验总结&#xff1a; 一、关于我 我的CSDN主页&#xff1a;https://gxdxyl.blog.csdn.net/ 2020年7月&#xff08;大二结束的暑假&#xff09;开始在CSDN写作&#xff1a; 阿里云博客专家&#xff1a; 接触的领域挺多的&#xff…

HTML 转 PDF API 接口

HTML 转 PDF API 接口 网络工具 / 文件处理 支持网页转 PDF 高效生成 PDF / 提供永久链接。 1. 产品功能 超高性能转换效率&#xff1b;支持将传递的 HTML 转换为 PDF&#xff0c;支持转换 HTML 中的 CSS 格式&#xff1b;支持传递网站 URL&#xff0c;直接转换页面成对应的 …

Java实现生成验证码实战

文章目录 需求描述思想思路实现代码实现效果 在实际项目中&#xff0c;管理端的登录&#xff0c;会涉及验证码的校验&#xff0c;简单的数字与字母组合形式&#xff0c;在Java中要如何生成与实现&#xff0c;记录下来&#xff0c;方便备查。 需求描述 生成8位的由数字、大写字…

【零基础学习CAPL】——CRC值监控测试

🙋‍♂️【零基础学习CAPL】系列💁‍♂️点击跳转 ——————————————————————————————————–—— 从0开始学习CANoe使用 从0开始学习车载车身 相信时间的力量 星光不负赶路者,时光不负有心人。 目录 1.概述2.需求介绍3.算法4.逻辑判断5.测…

ARCGIS PRO DSK MapTool

MapTool用于自定义地图操作工具&#xff0c;使用户能够在ArcGIS Pro中执行特定的地图交互操作。添加 打开MapTool1.vb文件&#xff0c;可以看到系统已经放出MapTool1类&#xff1a; Public Sub New()将 IsSketchTool 设置为 true 以使此属性生效IsSketchTool TrueSketchTyp…

为了准确计算延迟退休时间,我做了一个退休年龄计算器

延迟退休计算方法 原本退休分为三种情况&#xff0c;男性&#xff0c;女工人&#xff0c;女干部 男性&#xff1a;退休年龄为60岁。女干部&#xff1a;退休年龄为55岁。女工人&#xff1a;退休年龄为50岁。 现在延迟以后&#xff08;根据2024年9月13日公布的规则&#xff09…

一次开发,多端部署--实例二

一、视觉风格 1、分层参数 使用了分层参数后&#xff0c;当系统切换深色模式时&#xff0c;字体和背景也可以自适应。 Row() {Column() {Text(分层参数)// 分层参数在sysResource包&#xff0c;属于系统参数&#xff0c;全局可用.fontColor($r(sys_color.ohos_id_color_text_pr…

JavaScript模块化——ES6模块化规范

作者&#xff1a;CSDN-PleaSure乐事 欢迎大家阅读我的博客 希望大家喜欢 使用环境&#xff1a;vscode Chrome浏览器 1.ES6 1.1ES6介绍 ES6的全称是ECMAScript 6&#xff0c;也称为ES2015&#xff0c;是JavaScript的一个重要版本&#xff0c;它引入了许多新特性和改进&#xf…

云计算实训43——部署k8s基础环境、配置内核模块、基本组件安装

一、前期系统环境准备 1、关闭防火墙与selinux [rootk8s-master ~]# systemctl stop firewalld[rootk8s-master ~]# systemctl disable firewalldRemoved symlink /etc/systemd/system/multi-user.target.wants/firewalld.service. Removed symlink /etc/systemd/system/dbus…

云渲染与AI渲染分别是什么?两者的优势对比

云渲染和AI渲染是两种先进的渲染技术&#xff0c;它们各自具有独特的优势和应用场景。下面针对两种情况来简单说明下。 1、云渲染&#xff1a; - 定义&#xff1a;云渲染是一种利用远程服务器(云端)来处理和生成渲染效果的技术。它允许用户将计算密集型的任务转移到云端&#…

uniapp网络延迟优化之骨架屏

文章目录 前言uniapp网络延迟优化之骨架屏 一、骨架屏是什么&#xff1f;二、使用步骤1.在微信开发者工具生成骨架屏文件2.转成vue组件3.组件中使用4.效果展示4.开发时遇到的问题&#xff1f; 总结 前言 uniapp网络延迟优化之骨架屏 一、骨架屏是什么&#xff1f; 骨架屏的主…

C++ | Leetcode C++题解之第403题青蛙过河

题目&#xff1a; 题解&#xff1a; class Solution { public:bool canCross(vector<int>& stones) {int n stones.size();vector<vector<int>> dp(n, vector<int>(n));dp[0][0] true;for (int i 1; i < n; i) {if (stones[i] - stones[i -…

卷积神经网络经典模型架构简介

【图书推荐】《PyTorch深度学习与企业级项目实战》-CSDN博客 《PyTorch深度学习与企业级项目实战&#xff08;人工智能技术丛书&#xff09;》(宋立桓&#xff0c;宋立林)【摘要 书评 试读】- 京东图书 (jd.com) ImageNet是一个包含超过1 500万幅手工标记的高分辨率图像的数据…

Redis——常用数据类型List

目录 List列表常用命令lpushlpushxrpushrpushlrangelpoprpoplindexlinsertllenlremltrim key start stoplset 阻塞版本命令blpopbrpop list的编码方式list的应用 List列表 Redis中的list相当于数组&#xff0c;或者 顺序表&#xff0c;一些常用的操作可以通过下面这张图来理解…