专栏首页眯眯眼猫头鹰的小树杈leetcode327. Count of Range Sum

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.

这道题目是指,现有一个整数数组,并输入上界值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<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;
    }

思路二:分治法

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

    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麻烦,效果也非常好,而且代码...

    OpenCV学堂
  • 使用java数组,并开始封装我们自己的数组

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

    wfaceboss
  • 深度探秘 Java 8 函数式编程(上)

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

    芋道源码
  • LG抢占商用机器人市场份额,欲推出三款商用服务机器人 | 热点

    镁客网
  • 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获奖论文公布,引起了业内极大的关注。但除了这些获奖论文,还有众多精彩的论文值得一读。因此在大会期间,国内自动驾...

    机器之心

扫码关注云+社区

领取腾讯云代金券