Leetcode__1508. Range Sum of Sorted Subarray Sums
这一题是一道十分典型的二分查找与双指针的使用，题目的大意是，给出一个数组 \(nums\) , 我们可以通过该数组得到子数组, 子数组的大小从 1 到 \(n\), 因此有 \(\frac{n(n+1)}{2}\) 个不同的子数组, 然后我们要求这些子数组的和, 然后对这些子数组的和进行排序, 求排序后的数组的区间和, 那么这道题的结果就是一些子数组和 的和, 可能有一点拗口, 我们会用例子说明.
我们定义原数组为 \(nums\), 他的 \(\frac{n(n+1)}{2}\) 个子数组的和 构成新的有序数组为 \(SUM_{sub}\) , 例如 \(nums = [1,2,3,4]\), 那么我们可以计算得到 \(SUM_{sub} = [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]\) , 然后我们要在 \(SUM_{sub}\) 上求区间和, 传统的方式就是求得 \(SUM_{sub}\), 然后在区间 \([left: right]\) 上求和.
问题思路转换
我们要将定义重新捋一下, \(SUM_{sub}\) 是子数组的和, 并且 \(SUM_{sub}\) 是有序的, 那么 \(SUM_{sub}\) 的前缀和\(Prefix_{subsum}[k] =\sum_{i=0}^k SUM_{sub}[i]\)就表示在子数组的和当中的最小的 \(k\) 个元素之和, 我们要求的是 \(SUM_{sub}[left]\) 到 \(SUM_{sub}[right]\) 这部分的和, 也就等于 \(Prefix_{subsum}[right] - Prefix_{subsum}[left-1]\),