leetcode327. Count of Range Sum

miya 发布于2019-08-16 16:47 / 1976人阅读

摘要：接着计算所有子数组中元素的和，并判断是否位于数值区间内。因此，在对左右子数组进行排序后，以左子数组中的每一位作为开头，在右子数组中找到满足和区间的第一个值，和超过区间的第一个值。则二者的差即为横穿左右的满足条件的子数组个数。

题目要求

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.

这道题目是指，现有一个整数数组，并输入上界值upper和下界值lower，问数组中一共有多少组连续的子数组，其子数组中数字的和在上界和下界之内。

思路一：暴力循环

我们可以首先遍历一遍数组，计算子数组下标[0,i）的所有元素的和。根据该结果可以计算自数组[i,j)中所有元素的和。接着计算所有子数组中元素的和，并判断是否位于数值区间内。代码如下：

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

思路二：分治法

分治法的核心思路在于，将计算整个数组的符合条件的子数组的问题切分为子问题，将数组一分为二，并分别计算左子数组的符合条件的子数组个数，右子数组中符合条件的子数组个数和横穿左右数组的符合条件的子数组个数。
计算横穿左右的子数组个数的方法很有趣，这采用了归并排序的思想，即无论左子数组中的元素或是右子数组中的元素如何变动，横穿左右的子数组个数都不会受影响。因此，在对左右子数组进行排序后，以左子数组中的每一位作为开头，在右子数组中找到满足upper和lower区间的第一个值，和超过upper区间的第一个值。则二者的差即为横穿左右的满足条件的子数组个数。

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

云服务器私有云 Leetcod LeetCode range() Range

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/74188.html

327. Count of Range Sum

摘要：题目链接这题实际就是给定范围内的，的方法。注意一开始把加进去，考虑结果是的情况，还有要用型，以免会还是可以来做，要统计范围内的个数，就是用。 327. Count of Range Sum 题目链接：https://leetcode.com/problems... 这题实际就是给定范围内的range sum，divide and conquer的方法。一路计算prefixSum[0:i...

mj 2019-08-14 17:34 评论0 收藏0
[LeetCode] 4Sum & 4Sum II

摘要：和方法一样，多一个数，故多一层循环。完全一致，不再赘述， 4Sum Problem Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which ...

sydMobile 2019-08-14 15:42 评论0 收藏0
315. Count of Smaller Numbers After Self

摘要：题目链接的题，用来做，这种求有多少的题一般都是。里多加一个信息表示以为的节点数。也可以做，因为是统计有多少的，其实就是求从最小值到的。的是，要做一个映射，把的值映射到之间。所以先把给一下，用一个来做映射。还有的方法，参考 315. Count of Smaller Numbers After Self 题目链接：https://leetcode.com/problems... divi...

cnio 2019-08-14 17:34 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
[LeetCode] Path Sum (I & II & III)

摘要： 112. Path Sum Problem Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node...

张金宝 2019-08-19 11:09 评论0 收藏0