归并排序面试题——区间和的个数

简介: 归并排序面试题——区间和的个数

题目

给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中,值位于范围 [lower, upper] (包含 lower 和 upper)之内的区间和的个数 。区间和 S(i, j) 表示在 nums 中,位置从 i 到 j 的元素之和,包含 i 和 j (i ≤ j)。

力扣链接:区间和个数

前置知识

前缀和:

sum[i...j]=arr[0...j]-arr[0...i-1]

准备一个前缀和数组presum,长度和原数组长度一样。如下图:
在这里插入图片描述

问题转换

1.假设0~i位置整体累加和是X,求必须以i位置结尾的子数组,有多少个在[lower,upper],就等同于去求,i之前的所有前缀和中有多少前缀和在[X-upper,X-lower]上

2.原数组[lower,upper] —> 前缀和数组中的每一个X 求[X-lower,X-upper]

3 . 传进来的每一个前缀和数组 有多少个落在[X-lower,X-upper]

4 . 放在归并排序里面求

代码:

package com.harrison.class03;

/**
 * @author Harrison
 * @create 2022-02-24-22:01
 * @motto 众里寻他千百度,蓦然回首,那人却在灯火阑珊处。
 */
public class Code05_CountOfRangeSum {
    public static int countRangeSum(int[] nums,int lower,int upper){
        if(nums==null || nums.length==0){
            return 0;
        }
        long[] sum=new long[nums.length];
        sum[0]=nums[0];
        for(int i=1; i<nums.length; i++){
            sum[i]=sum[i-1]+nums[i];
        }

        return process(sum,0,nums.length-1,lower,upper);
    }

    // arr[L...R]已经不传进来了,只传进来sum(前缀和数组!!!)
    // 求在原始数组arr[L...R]中,有多少个子数组累加和在[lower,upper]上
    public static int process(long[] sum, int L, int R, int lower, int upper){
        if(L==R){
            return sum[L]>=lower && sum[L]<=upper?1:0;
        }
        // L!=R 范围上不止一个位置
        int M=L+((R-L)>>1);
        return process(sum,L,M,lower,upper)+
                process(sum,M+1,R,lower,upper)+
                merge(sum,L,M,R,lower,upper);
    }

    public static int merge(long[] sum,int L,int M,int R,int lower,int upper){
        int ans=0;
        int windowL=L;
        int windowR=L;
        // [windowL,windowR)
        for(int i=M+1; i<=R; i++){
            long min=sum[i]-upper;
            long max=sum[i]-lower;
            while(windowR<=M && sum[windowR]<=max){
                windowR++;
            }
            while(windowL<=M && sum[windowL]<min){
                windowL++;
            }
            ans+=windowR-windowL;
        }
        long[] help=new long[R-L+1];
        int i=0;
        int p1=L;
        int p2=M+1;
        while(p1<=M && p2<=R){
            help[i++]=sum[p1]<=sum[p2]?sum[p1++]:sum[p2++];
        }
        while(p1<=M){
            help[i++]=sum[p1++];
        }
        while(p2<=R){
            help[i++]=sum[p2++];
        }
        for(i=0; i<help.length; i++){
            sum[L+i]=help[i];
        }
        return ans;
    }
}
相关文章
|
12月前
第k小的数(2种快排解法、1种堆排解法)
第k小的数(2种快排解法、1种堆排解法)
59 0
|
6月前
|
人工智能 算法
图解:求逆序对数量(归并排序的应用)
图解:求逆序对数量(归并排序的应用)
|
人工智能 算法
【归并排序】归并排序/逆序对的数量
【归并排序】归并排序/逆序对的数量
|
算法 测试技术 C++
C++算法:二分查找旋转数组
C++算法:二分查找旋转数组
|
算法
【快速排序】快速排序/第k个数
【快速排序】快速排序/第k个数
|
算法 搜索推荐
|
算法 C++
快排例题——第k个数
做道简单一点的题巩固一下
|
存储 人工智能
归并排序例题——逆序对的数量
做道简单一点的题巩固一下
(归并排序)AcWing 788. 逆序对的数量
(归并排序)AcWing 788. 逆序对的数量
81 0