题目描述
给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
示例 1：
输入：nums = [-2,5,-1], lower = -2, upper = 2
输出：3
解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。
示例 2：
输入：nums = [0], lower = 0, upper = 0
输出：1
思路:
根据例子可知 解答题意如下
输入：nums = [-2,5,-1], lower = -2, upper = 2
区间和就是从0位置上的数到i位置上面的数
所以【-2,5,-1】其实就是
下面以0结尾的数
0-0 -2
下面是以1结尾的数
0-1 区间和是-2+5=3
1-1 区间和是5
下面是以2为结尾的区间和
0-2 区间和是-2+5±1=2
1-2 区间和是5-1=4
2-2 区间和是-1
所以最后满足题意的[0,0]、[2,2] 和 [0,2] 对应的区间和分别是：-2 、-1 、2 。
本题思路
* * * 首先用到了前缀和数组，前缀和presum[i]表示从0到i数组元素的和 * 之后问题可以转化为：求解(i,j)使得presum(j)-presum(i)∈[lower,upper] * 因为例如2-5的区间和，就用前缀和来表示就是0到5的累加减去0到2的累加 * 也即前缀和presum(5)-presum(2) * 所以之后问题可以转化为：求解(i,j)使得presum(j)-presum(i)∈[lower,upper] * 最直观的解法当然是双指针暴力解，遍历数组来进行逐个查找 * * 假设0-i整体累加和是x,求必须以i位置结尾的子数组，目标有多少个在【l,up】范围上 * 等同于去求i之前的所有前缀和中有多少个前缀和在【x-up,x-l】上 * * 题目转化成在前缀和数组中【，，，x,y,z】例如求以x结尾的数落在【L，up]上 * 转出成在x之前有多少数落在【x-up,x-l】 * 就是求x之前的一个指标 在【x-up,x-l】上 * * 即利用归并排序求解 * i,j在同一边（同在左边或同在右边） i、j分别在左右数组中 对于第一种情况，可以考虑直接递归求解， 将问题最终递归到左右数组各只有一个元素的情形，结果ret=左递归+右递归 * merge过程因为右组都是减去upper和lower且右组是有序的 * 所以左组中数据是不回退 所以时间复杂度是O(N)的 窗口左边界和右边界只会向右，不会回退 * 这是个规律 可以举例看出来 *
AC代码
import java.util.Scanner; public class code15_CountOfRangeSum { //计算区间和的主方法 public static int countRangeSum(int[] nums, int lower, int upper) { //如果数组为空的话直接返回值为0 if (nums == null || nums.length == 0) { return 0; } //统计前缀和，生成前缀和数组 用long类型，防止溢出 //新建一个数组来存放前缀和 long[] sum = new long[nums.length]; //0——0的前缀和就是0位置上的数 sum[0] = nums[0]; //计算全部的前缀和 for (int i = 1; i < nums.length; i++) { sum[i] = sum[i - 1] + nums[i]; } //对前缀和数组，从0开始到最后利用归并排序，在merge的同时结算答案 return process(sum, 0, sum.length - 1, lower, upper); } // 返回preSumArr[L...R]上，区间累加和满足条件的个数 public static int process(long[] sum, int L, int R, int lower, int upper) { //如果左边等于右边表示的是，前缀和中只有一个数 //所以如果这个数满足lower=<数<=upper 则返回1 否则返回0 if (L == R) { return sum[L] >= lower && sum[L] <= upper ? 1 : 0; } //计算中点 >>表示右移一位 表示除以2取整 int M = L + ((R - L) >> 1); //左区、右区分别递归，结算各自区间上的答案 int left = process(sum, L, M, lower, upper); int right = process(sum, M + 1, R, lower, upper); for (int i = 0; i < sum.length; i++) { System.out.println(sum[i]); } //此时左区和右区已经分别有序，左右两区merge，结算左右整体的答案： int merge = merge(sum, L, M, R, lower, upper); // System.out.println(left); // System.out.println(right); // System.out.println(merge); return left+right+merge; } // preSumArr[L...M] merge preSumArr[M+1...R] // 左区merge右区，返回符合条件的个数 public static int merge(long[] arr, int L, int M, int R, int lower, int upper) { int ans = 0; //左右区互相归并 //定义窗口的左右边界 int windowL = L; int windowR = L; // [windowL, windowR) //遍历右组的数 计算前缀和i位置中有多少值落在 【x-upper----x-lower】之间 for (int i = M + 1; i <= R; i++) { //当前值-upper作为最小值 //当前值-lower作为最大值 long min = arr[i] - upper; long max = arr[i] - lower; //窗口左边界和右边界只会向右 while (windowR <= M && arr[windowR] <= max) { windowR++; } //窗口左边界和右边界只会向右 while (windowL <= M && arr[windowL] < min) { windowL++; } //每一步都累加到ans上面 ans += windowR - windowL; } //正常merge为了让其有序 //创建一个新的数组 以下是经典的归并排序的merge的代码 long[] help = new long[R - L + 1]; int i = 0; int p1 = L; int p2 = M + 1; //归并的过程 while (p1 <= M && p2 <= R) { help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; } while (p1 <= M) { help[i++] = arr[p1++]; } while (p2 <= R) { help[i++] = arr[p2++]; } //写回help数组 for (i = 0; i < help.length; i++) { arr[L + i] = help[i]; } return ans; } //计算区间和 public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.next().toString(); String[] arr = s.split(","); int[] nums = new int[arr.length]; for(int j = 0; j<nums.length;j++) { nums[j] = Integer.parseInt(arr[j]); // System.out.println(b[j]); } int a = sc.nextInt(); int b = sc.nextInt(); int sum = countRangeSum(nums, a, b); System.out.println(sum); } }
