leetcode Count of Range Sum

leetcode Count of Range Sum

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (ij), inclusive.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.

题目地址: leetcode Count of Range Sum

题意:

给定一个整数组成的数组,求它的所有子区间和坐落于[lower, upper] 的个数。

比如样例中[-2, 5, -1]中,这三个区间的和在[-2,2]之间 [0, 0], [2, 2], [0, 2]

思路

先来看看最朴素的O(n^2)算法,首先算出和,然后枚举区间范围。

 

题目要求的效率好于O(n^2)的算法,那么要怎么加速呢?

还记得 Count of Smaller Numbers After Self  么?

那时候,我们用Fenwick树或者线段树,先离散化,然后从右向左扫描,每扫描一个数,对小于它的求和。然后更新…..

这题也差不多,需要找满足条件 lower ≤ sum[j] – sum[i – 1] ≤ upper ,也就是lower + sum[i – 1] ≤ sum[j] ≤ upper + sum[i – 1]

我们同样的求出和,然后离散化,接着从右向左扫描,对每个i 查询满足在[ lower + sum[i – 1], upper + sum[i – 1] ]范围内的个数(用线段树或者Fenwick Tree)

这样复杂度就是O(n log n)

 

线段树

C++ 

 

Binary indexed tree (Fenwick tree)

关于此树的介绍: Binary indexed tree (Fenwick tree) 

注意要加入upper 和 lower -1 两个点

(python 版本比C++简洁太多了^ ^,建议看py版本)

 

C++

 

Python

 

 

本文是 leectode 327 Count of Range Sum 的题解,

更多leetcode题解见 https://www.hrwhisper.me/leetcode-algorithm-solution/

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Count of Range Sum
本文地址:https://www.hrwhisper.me/leetcode-count-of-range-sum/

听说长得好看的已经打赏了

Leetcode , , , , . permalink.

18 thoughts on “leetcode Count of Range Sum

  1. Fenwick Tree的C++解法,从52行开始不太明白,为什么要从后往前做循环呢? 希望作者能解释一下,谢谢。

  2. 有个问题,可能是我对树状数组理解不深,就是如果是数组中间的一部分在区间里面,这个是怎么计算进去的,因为我看每次total都是减去末尾的一个元素,然后重复下去,这样子每次add和sum不都是算从头到当前位置那部分的吗?谢谢。

    • 抱歉回复晚了. 树状数组就是每次计算的从头到当前位置的和。 你可以看博客中关于树状数组的介绍 (本文就有链接啦)

      • 恩。。。那到底是怎么考虑进去数组中间的一部分和到底符不符合要求呢。。。我理解能力差。。。看到网上就你写的关于这道题比较全面,麻烦你的回答了~

        • 数组中间是否满足要求? 不是求 lower ≤ sum[j] – sum[i – 1] ≤ upper => lower + sum[i – 1] ≤ sum[j] ≤ upper + sum[i – 1] 么? 每次对区间进行查询啊 在区间的就是符合要求的。

Leave a Reply

Your email address will not be published. Required fields are marked *