LeetCode[327]区间和的个数

这篇具有很好参考价值的文章主要介绍了LeetCode[327]区间和的个数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

难度:Hard

题目:

给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中,值位于范围 [lower, upper] (包含 lower 和 upper)之内的 区间和的个数 。

区间和 S(i, j) 表示在 nums 中,位置从 i 到 j 的元素之和,包含 i 和 j (i ≤ j)。


示例 1:

输入:nums = [-2,5,-1], lower = -2, upper = 2
输出:3
解释:存在三个区间:[0,0]、[2,2] 和 [0,2] ,对应的区间和分别是:-2 、-1 、2 。

 示例 2:

输入:nums = [0], lower = 0, upper = 0
输出:1

提示:

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • -105 <= lower <= upper <= 105
  • 题目数据保证答案是一个 32 位 的整数

 Related Topics

  • 树状数组
  • 线段树
  • 数组
  • 二分查找
  • 分治
  • 有序集合
  • 归并排序

重点!!!解题思路

明确解题思路: 

      (1)题目要求求出区间和,根据区间和即可想到前缀和

      (2)那么将此题简化,前缀和相减即为区间和,这样即可列出一个式子:假设前缀和数组为nums,那么区间和为nums[j]-nums[i],加上区间和范围即lower<=nums[j]-nums[i]<=upper

      (3)式子继续简化nums[j]-lower>=nums[i]>=nums[j]-upper,通过式子可以看出如果我们能固定j的位置即可求出i的位置范围a<=nums[i]<=b

      (4)这样通过找到a和b的范围,即可确定在a和b的区间和个数为b-a+1

      (5)如果想j再往后走一位,这时如果nums[j+1]>nums[j] 那么根据公式我们nums[j+1]的a和b一定大于nums[j]的a和b

      (6)那么我们如何保证nums[j+1]一定大于nums[j]呢 这时我们就可以联想到归并排序了,因为归并排序的时候就是先分开递归再并在一起排序

      (7)明白以上思路 即可做题了

源码+讲解:

    class Solution {
        long[] temp;

        public int countRangeSum(int[] nums, int lower, int upper) {
            long[] sum = new long[nums.length + 1];
            temp = new long[nums.length + 1];
            sum[0] = 0;
            for (int i = 0; i < nums.length; i++) sum[i + 1] = sum[i] + nums[i];  //求一个前缀和数组
            return merge_sort(sum, 0, sum.length - 1, lower, upper);  //我们归并排序的就是一个前缀和数组
        }
        //这里就是一个很基础的归并排序,不懂得朋友请看本章节的其他题巩固一下
        public int merge_sort(long[] sum, int l, int r, int lower, int upper) {
            if (l >= r) return 0;
            int mid = (l + r) >> 1, ans = 0;
            ans += merge_sort(sum, l, mid, lower, upper);
            ans += merge_sort(sum, mid + 1, r, lower, upper);
            ans += countTwoPart(sum, l, mid, mid + 1, r, lower, upper);  //在合并前进行区间和个数的判断
            int k = l, p1 = l, p2 = mid + 1;
            while (p1 <= mid || p2 <= r) {
                if (p2 > r || (p1 <= mid && sum[p1] < sum[p2])) {
                    temp[k++] = sum[p1++];
                } else {
                    temp[k++] = sum[p2++];
                }
            }
            for (int i = l; i <= r; i++) sum[i] = temp[i];
            return ans;
        }

        public int countTwoPart(long[] sum, int l1, int r1, int l2, int r2, int lower, int upper) {
            int k1 = l1, k2 = l1, ans = 0;
            for (int j = l2; j <= r2; j++) {  //通过固定模拟nums[j]的位置来计算k1,k2的边界
                long a = sum[j] - upper;
                long b = sum[j] - lower;
                while (k1 <= r1 && sum[k1] < a) k1++;  //k1移动到a的位置
                while (k2 <= r1 && sum[k2] <= b) k2++;  //k2移动到b+1的位置
                ans += k2 - k1;  //得到k1,k2的边界,其中k1-k2就是区间和个数
            }
            return ans;
        }
    }

运行结果:

LeetCode[327]区间和的个数,算法刷题篇,快速排序,# 归并排序(Merge-Sort):从二路到多路,leetcode,算法,排序算法

如果您还有什么疑问或解答有问题,可在下方评论,我会及时回复。

系列持续更新中,点个订阅吧,喜欢练习算法那就点个攒吧 文章来源地址https://www.toymoban.com/news/detail-610076.html

到了这里,关于LeetCode[327]区间和的个数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【leetcode 力扣刷题】汇总区间//合并区间//插入区间

    题目链接:228.汇总区间 题目内容: 看题目真是没懂这个题到底是要干啥……实际上题目要求的 恰好覆盖数组中所有数字 的 最小有序 区间范围列表,这个最小是指一个区间范围小。比如能够覆盖{2,3,4,6}的区间可以是[2,6],但是5在区间内,却不在数组内,因此这个区间不是最

    2024年02月10日
    浏览(38)
  • LeetCode 刷题 数据结构 数组 485 最大连续1的个数

    给定一个二进制数组  nums  , 计算其中最大连续  1  的个数。 示例 1: 示例 2: 提示: 1 = nums.length = 105 nums[i]  不是  0  就是  1.   参看bilibli视频-up主 爱学习的饲养员,讲解的很清晰。 手把手带你刷Leetcode力扣|各个击破数据结构和算法|大厂面试必备技能【已完结】-

    2024年02月15日
    浏览(51)
  • 「优选算法刷题」:有效三角形的个数

    给定一个包含非负整数的数组  nums  ,返回其中可以组成三角形三条边的三元组个数。 示例 1: 示例 2: 这道题,有一点挺新鲜的:构成三角形的三条边,仅需满足 2 条最短边之和大于等于第三条边即可。 以前的罗根,就总是傻傻地求 3 次😭 今天这道题,算是又打开了我新世

    2024年01月20日
    浏览(38)
  • 算法训练day36|贪心算法 part05(重叠区间三连击:LeetCode435. 无重叠区间763.划分字母区间56. 合并区间)

    题目链接🔥🔥 给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。 示例 1: 输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1 解释: 移除 [1,3] 后,剩下的区

    2024年02月09日
    浏览(62)
  • 78-快速排序练习-LeetCode面试题17.14.最小k个数

    题目 设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。 示例: 输入: arr = [1,3,5,7,2,4,6,8], k = 4 输出: [1,2,3,4] 提示:     0 = len(arr) = 100000     0 = k = min(100000, len(arr)) 思路 注意到题目要求「任意顺序返回这 k 个数即可」,因此我们只需要确保前 k 小的

    2023年04月12日
    浏览(32)
  • 【算法之贪心算法IV】leetcode56. 合并区间

    力扣题目链接 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中 points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend 之间的气球。你不知道气球的确切 y 坐标。 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭

    2024年02月11日
    浏览(58)
  • 【刷题篇】栈和队列

    目录 一.前言🌈 二.有效的括号✨ a.题目 b.题解分析 c.AC代码  三. 用队列实现栈📏 a.题目 b.题解分析(辅助队列法) c.AC代码(辅助队列法) d.题解分析(就地存储法) c.AC代码(就地存储法) 四. 用栈实现队列🍀 a.题目 b.题解分析 c.AC代码         各位小友们好久不见,甚

    2024年02月02日
    浏览(49)
  • 【刷题篇】链表(上)

    前段时间我们学习了单向链表和双向链表,本期将带来3道与链表相关的OJ题来巩固对链表的理解。话不多说,让我们进入今天的题目吧! 🚀本期的题目有: 反转单链表 、 链表的中间结点 、 合并两个有序链表 a.题目 b.题解分析(迭代) 🍡 三指针法: 我们可以直接在原链表的

    2024年02月02日
    浏览(56)
  • 【刷题篇】链表(下)

    各位读者们好,本期我们来填填之前留下的坑,继续来讲解几道和链表相关的OJ题。但和上期单向链表不一样的是,我们今天的题目主要是于环形链表有关,下面让我们一起看看吧。 💻本期的题目有: 环形链表 、 环形链表II 、 求环形链表环长 a.题目 b.题解分析 第一种方法

    2024年01月25日
    浏览(43)
  • 蓝桥杯刷题篇①

    前言:hello各位童学们好呀!许久不见!本文为本人的蓝桥杯OJ的刷题笔记!文章隶属于专栏蓝桥杯,该专栏的目的是为了记录自己的刷题记录和学习过程,激励自己不断前行,为明年的ACM、ICPC、蓝桥杯等比赛做足准备,也希望可以帮助到一些同样在刷题道路上的小伙伴们!

    2024年02月09日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包