本文源于20201107 leetcode每日一题，探讨了对归并排序中涉及的【局部有序】思想的再次思考

327. 区间和的个数

给定一个整数数组 nums，和上下界lower, upper。数组nums可能存在某个区间的和位于[lower, upper]之间。找到所有区间和处于[lower, upper]之间的区间，返回这样的区间的总个数

输入: nums = [-2,5,-1], lower = -2, upper = 2,
输出: 3
解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: -2, -1, 2，位于[-2, 2]之间

分析

题目即找到所有这样的i, j，i<j，形成区间[i, j)，
满足 lower <= sum(nums[i:j]) <= upper

1.最基本解法-暴力

暴力呗，二层循环遍历完所有的i,j组合，计算sum(nums[i:j])进行判断。以下java代码，有个trick：对于每个i，初始化sum为0，通过sum += nums[j]更新sum，减少重复计算。（注：这里leetcode java暴力能过，python过不了）

class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            long sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (lower <= sum && sum <= upper) {
                    count++;
                }
            }
        }
        return count;
    }
}

2.归并思想解法

我们知道，要覆盖完数组nums所有的[i, j)，在再没有其他条件的情况下，只能够进行O(n^2)的二层遍历，遍历是跑不掉的。要优化的话，必然要加入其他条件，达到一些类似剪枝的效果，如对于某个i，当j到达一个界限时，前面或者后续的j都不会满足题意，从而剪枝。那么，进行如下考虑：

• 1.首先，对于求解sum(nums[i:j])，我们有一个常见的优化解法是利用前缀和。即计算presum数组，presum[i]表示sum(nums[:i])，那么sum(nums[i:j]) = presum[j] - presum[i]。这里我们也用presum数组来计算任一区间和
• 2.先假设presum是有序的，然后将presum从中部划分为left_part和right_part两部分。那么对于当前规模的presum，i, j的分布将出现3种case

case	left_part	right_part
0	i	j
1	i,j
2		i,j

我们需要考虑i,j的3种分布case，才能够正确地解决当前presum数组对应的问题。注意到，case1 和 case2 可以看成新的子问题，即presum的left_part对应的子问题为case1，presum的right_part对应的子问题为case2。而case1和case2的解决又可以继续再分为类似的3个case

解决当前规模问题
= 解决3个case
= 解决case1-left_part子问题 + 解决case2-right_part子问题 + 解决case0-融合left_part和right_part

试着将其写成伪代码看一下

def solve(presum):
    solve(left_part)   # case1
    solve(right_part)   # case2 
    something done to left_part and right_part   # case0

——很直观，有点像【归并排序】的样子吧：
归并排序不断将大数组分成两个数组，我们就可以理解成左半部分和右半部分，先将左右部分排好，类似解决case1和case2，然后可以进一步想成左边对应着 i，右边对应着 j，即case0。

在left_part和right_part都有序的情况下，我们在right_part中维护2个指针low_index和up_index来标记j的合法上下界，对left_part的每一个元素，都在right_part中线性地找到对应的low_index和up_index，其差值up_index-low_index即为当前left_part[i]起始的所有合法区间

• 3.上面的讨论基于我们假设presum是有序的，但很多情况下presum都是无序的。怎么办？事实上，只需要保证left_part和right_part内部有序，并且left_part中的任一前缀和对应原数组的下标 i 小于 right_part中的任一前缀和对应原数组的下标 j 即可。因为从伪代码来看，我们需要做的所有事情就是求出case0即i,j左右分布时满足题意得[i, j)个数，其他的交给递归代码就好。也就是说，对于原数组而言，若要找出全部的下标对数量，只需要找出左端点在左侧数组，同时右端点在右侧数组的下标对数量。因此，我们可以模仿归并排序对presum进行逐步的局部排序，实现left_part和right_part内部有序，并保证i < j

综上分析，有以下python代码。排序部分做了一个小trick，直接调接口sorted()，没按归并写法写

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        # 计算前缀和presum，对presum进行归并排序，在归并排序的过程中，统计符合条件的i j 对

        # 1.计算所有前缀和, presum[i]表示sum(nums[:i])
        presum = [0]
        s = 0
        for ele in nums:
            s += ele
            presum.append(s)
        
        res = 0
        # 2.对presum进行归并排序，在归并排序的过程中，统计符合条件的i j 对
        def mergeSortCount(presum):
            nonlocal res
            l = len(presum)
            # 递归出口
            if l == 0 or l == 1:
                return presum
            mid = l // 2
            # 获取内部有序的左右两部分
            left_part = mergeSortCount(presum[:mid])
            right_part = mergeSortCount(presum[mid:])
            ### 核心代码 —— 统计i, j对 ###
            # 对left_part的每一个元素，在right_part中查找到上下界元素
            low_index, up_index = 0, 0
            for ele in left_part:
                while low_index < len(right_part):
                    if right_part[low_index] - ele < lower:
                        low_index += 1
                    else:
                        break
                while up_index < len(right_part):
                    if right_part[up_index] - ele <= upper:
                        up_index += 1
                    else:
                        break
                res += (up_index - low_index)
            ### 核心代码 —— 统计i, j对 ###

            # 统计完后进行归并排序，为了简单起见这里就直接sort，不写归并的代码了
            return sorted(presum)
        
        mergeSortCount(presum)
        return res