我月入5万+，相亲遇到一女的，她工资5千不到，要求我给彩礼入赘养她一家人，还要我长得帅。。。

你有没有遇到过这种面试题，一看上去挺眼熟，但真写起来总感觉细节缝缝太多，怎么都不放心？

我前阵子就碰到了这么一道题：

给定一个整数数组 nums 和两个整数 lower 和 upper，返回数组中 区间和 在 [lower, upper] 范围内的个数。

你要我说，这道题看起来像前缀和，做起来像归并排序，调起来像是在找 bug 😵。

先讲点人话，题目要求我们找出所有符合要求的子数组 [i, j]，使得 sum(nums[i] + ... + nums[j]) 落在 [lower, upper] 之间。这个“子数组区间和”一出来，就该想到老朋友——前缀和。

搞个前缀和数组 preSum，preSum[i] 表示 nums[0] 到 nums[i - 1] 的和。于是原问题就变成了在所有 (i, j) 中，找出 preSum[j] - preSum[i] 在 [lower, upper] 范围内的对数。

这不就像是在问：对于每一个前缀和，前面有多少个前缀和落在某个区间内。是不是很像逆序对？

然后，你就知道，这活用暴力写是没戏的，O(n²) 肯定超时（Leetcode会亲切地送你一个 TLE）。

所以得上点硬菜——归并排序的思想来干这事，归并时统计区间个数，外加原地排序。

我贴一下 Java 的核心逻辑代码（别担心，我尽量压缩了，不烧脑）：

publicintcountRangeSum(int[] nums, int lower, int upper) {
long[] preSum = newlong[nums.length + 1];
for (inti=0; i < nums.length; i++) {
        preSum[i + 1] = preSum[i] + nums[i];
    }
return countWhileMergeSort(preSum, 0, preSum.length, lower, upper);
}

privateintcountWhileMergeSort(long[] sum, int left, int right, int lower, int upper) {
if (right - left <= 1) return0;
intmid= (left + right) / 2;
intcount= countWhileMergeSort(sum, left, mid, lower, upper)
              + countWhileMergeSort(sum, mid, right, lower, upper);
intj= mid, k = mid, t = mid;
long[] cache = newlong[right - left];
intr=0;
for (inti= left; i < mid; i++) {
while (k < right && sum[k] - sum[i] < lower) k++;
while (j < right && sum[j] - sum[i] <= upper) j++;
while (t < right && sum[t] < sum[i]) cache[r++] = sum[t++];
        cache[r++] = sum[i];
        count += j - k;
    }
    System.arraycopy(cache, 0, sum, left, t - left);
return count;
}

代码不短，但逻辑其实很清晰。你要是愿意花点时间捋一捋，会发现它就是个“归并排序 + 双指针 + 区间统计”。

简单解释下这个黑魔法是怎么来的：

1. 1. 把前缀和分成两半，各自递归统计（这个没啥好说的）；
2. 2. 在归并的时候，统计有多少对 (i, j) 满足 sum[j] - sum[i] ∈ [lower, upper]；
3. 3. 归并还顺手维护了 sum 数组的有序性，为下一轮递归做好准备。

我一开始对这段代码还有点抗拒，但后来想通了，其实跟日常开发一个道理：当你意识到 O(n²) 不行，那就得动点脑筋让它“偷懒”，只不过这回偷懒的是“借助排序来顺便统计”。

说句实话，这道题乍一看挺数学，但解决方案却是程序员最熟悉的套路：拆问题、递归、排序、统计——一个不少，硬生生把复杂问题拆得井井有条。就像我们日常修 bug，一边输出，一边调试，一边嘀咕：你倒是给点提示啊😤。

所以结论就一个：
能用前缀和的题，不要怕搞归并；归并不仅能排序，还能帮你省下很多时间复杂度。

最后讲个题外话。有次我跟朋友喝酒聊起这道题，他跟我说：“这不是统计区间和嘛，我暴力跑一遍就好了！”我看着他杯子里泡着两根花生米，也没忍心打击他——兄弟，你以为是牛肉面买一碗送一碗，这可是面试题，考的是你能不能在10分钟内写出正确且高效的解法。

毕竟面试官的微笑永远留给优化到 O(n log n) 的人，暴力解法只配一张感谢参与奖🎁。

别嫌麻烦，动点脑筋，面试场上这就是加分题。再说了，你写代码，不就是为了装杯嘛？