# leetcode327. 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 (i ≤ j), inclusive.

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

Example:

Input: nums = [-2,5,-1], lower = -2, upper = 2,
Output: 3
Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.```

## 思路一：暴力循环

```    public int countRangeSum(int[] nums, int lower, int upper) {
long[] sums = new long[nums.length+1];
for(int i = 0 ; i<nums.length ; i++) {
sums[i+1] = sums[i] + nums[i];
}

int count = 0;
for(int i = 0 ; i<nums.length ; i++) {
for(int j = i+1 ; j<=nums.length ; j++) {
if(sums[j] - sums[i] >= lower && sums[j] - sums[i] <= upper) {
count++;
}
}
}
return count;
}```

## 思路二：分治法

```    public int countRangeSum3(int[] nums, int lower, int upper) {
long[] sums = new long[nums.length + 1];
for(int i = 0 ; i<nums.length ; i++) {
sums[i+1] = sums[i] + nums[i];
}
long[] sortedSums = new long[nums.length + 1];
return mergeCountRangeSum3(sums, sortedSums, 0, nums.length+1, lower, upper);
}

public int mergeCountRangeSum3(long[] sums,long[]  sortedSums, int start, int end, int lower, int upper) {
if(end - start <= 1) return 0;
int mid = (start + end) / 2;
int count = mergeCountRangeSum3(sums, sortedSums, start, mid, lower, upper)
+ mergeCountRangeSum3(sums, sortedSums, mid, end, lower, upper);
int firstLargerThanUpper = mid, firstLargerThanLower = mid, indexOfRightHalf = mid;
for(int i = start, sortedSumsIndex = start; i < mid ; i++, sortedSumsIndex++) {
while(firstLargerThanUpper < end && sums[firstLargerThanUpper] - sums[i] <= upper)  firstLargerThanUpper++;
while(firstLargerThanLower < end && sums[firstLargerThanLower] - sums[i] <lower) firstLargerThanLower++;
while(indexOfRightHalf < end && sums[indexOfRightHalf] < sums[i]) sortedSums[sortedSumsIndex++] = sums[indexOfRightHalf++];
sortedSums[sortedSumsIndex] = sums[i];
count += firstLargerThanUpper - firstLargerThanLower;
}
System.arraycopy(sortedSums, start, sums, start, indexOfRightHalf - start);
return count;
}```

0 条评论

• ### leetcode540. Single Element in a Sorted Array

You are given a sorted array consisting of only integers where every element app...

• ### leetcode523. Continuous Subarray Sum

Given a list of non-negative numbers and a target integer k, write a function to...

• ### leetcode410. Split Array Largest Sum

将一个长度为n的正整数数组分割为m个非空的连续子数组，并分别计算每个子数组中所有元素的和。求一种分割方式，使得该分割方式生成的最大子数组和为所有分割方式中最小的...

• ### BBAVectors：一种Anchor Free的旋转物体检测方法

WACV2021的一篇文章，将CenterNet的方案用到了旋转物体的检测中，设计了一种精巧的旋转框表达方式，免去了设计anchor麻烦，效果也非常好，而且代码...

• ### 使用java数组，并开始封装我们自己的数组

今天感冒了，全身酸软无力，啥样不想做，就来学习吧，此节我们从初步使用java中提供的数组，然后分析相关情况，过渡到封装我们自己的数组。

• ### 深度探秘 Java 8 函数式编程（上）

怎样在一行代码里同时计算一个列表的和、最大值、最小值、平均值、元素个数、奇偶分组、指数、排序呢？

• ### Android配置EGL环境

Android配置egl环境我们根据GLSurfaceView源码来实现。在GLSurfaceView源码里面，当调用setRenderer的时候会开启一个线程...

• ### VelocityTracker的用法

Helper for tracking the velocity of touch events, for implementing flinging and ...

• ### 专栏 | CVPR 2017论文解读：特征金字塔网络FPN

机器之心专栏 作者：李俊 近日，CVPR 2017获奖论文公布，引起了业内极大的关注。但除了这些获奖论文，还有众多精彩的论文值得一读。因此在大会期间，国内自动驾...