侧边栏壁纸
博主头像
mkdir700博主等级

思考人生意义的码农

  • 累计撰写 31 篇文章
  • 累计创建 43 个标签
  • 累计收到 2 条评论

目 录CONTENT

文章目录

1508. 子数组和排序后的区间和

mkdir700
2022-09-11 / 0 评论 / 2 点赞 / 87 阅读 / 5,113 字 / 正在检测是否收录...

描述

给你一个数组 nums ,它包含 n 个正整数。你需要计算所有非空连续子数组的和,并将它们按升序排序,得到一个新的包含 n * (n + 1) / 2 个数字的数组。

请你返回在新数组中下标为 left 到 right **(下标从 1 开始)**的所有数字和(包括左右端点)。由于答案可能很大,请你将它对 10^9 + 7 取模后返回。

示例 1:

输入:nums = [1,2,3,4], n = 4, left = 1, right = 5
输出:13 
解释:所有的子数组和为 1, 3, 6, 10, 2, 5, 9, 3, 7, 4 。将它们升序排序后,我们得到新的数组 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 1 到 ri = 5 的和为 1 + 2 + 3 + 3 + 4 = 13 。

示例 2:

输入:nums = [1,2,3,4], n = 4, left = 3, right = 4
输出:6
解释:给定数组与示例 1 一样,所以新数组为 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 3 到 ri = 4 的和为 3 + 3 = 6 。

示例 3:

输入:nums = [1,2,3,4], n = 4, left = 1, right = 10
输出:50

提示:

  • 1 <= nums.length <= 10^3
  • nums.length == n
  • 1 <= nums[i] <= 100
  • 1 <= left <= right <= n * (n + 1) / 2

标签
#前缀和 #二分查找 #数组 #排序

相似题目


题解

0x01 前缀和 + 暴力遍历

最简单的做法就是按题目要求模拟,长度为 n 那就模拟 n 个子数组(前缀和),然后拼接成一个新数组,将新数组按升序排序,再通过切片求和即可。

nums = [1, 2, 3, 4], left = 3, right = 4 为例

图示:

代码:

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        sums = []
        for i in range(len(nums)):
            sums += list(itertools.accumulate(nums[i:]))
        sums.sort()
        return sum(sums[left-1:right]) % (10**9 + 7)

0x02 前缀和 + 二分查找

nums 排序,然后将其前缀和子数组排列开来,就是半个矩阵,如图所示:

这个矩阵有如下特点:

  • 从左往右单调递增
  • 从上往下单调递增

题目要求算出 [left, right] 的和,问题可以转换成:

  • [0, left] 的和 leftSum
  • [0, right] 的和 rightSum
  • rightSum - leftSum 就是答案;

来几张图一目了然:

两者相减:

  • left 表示求矩阵的前 left - 1 个数
  • right 表示求矩阵的前 right 个数

通过上面的分析,将问题转换成了查找一个矩阵的前 K 个元素之和,但是前提条件是得把所有元素计算出来排列成一个矩阵,如果是这样,那我还不如直接暴力求解了呢。

我们求的是什么,是,并不是某个单独的元素,即使从矩阵找到这些元素也是为了求

官方题解告诉我们求前缀和的前缀和,然后一系列操作,我太菜了,是直接看懵逼了。


先来理一理这个前缀和数组与矩阵之间藏着什么猫腻。

首先得搞明白一件事,给我们一个前缀和数组 sums = [1, 3, 6, 10],它是数组 arr = [1, 2, 3, 4] 的前缀和,问,如何通过前缀和求出算出其他元素?

换一种描述,数组 arr 排列出来所有的前缀和为 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10],试过第一种方法对这个结果应该不会陌生吧,为了方便下文引用,就叫这个长长的数组为 long_arr

好,那现在的问题是,通过 sums = [1, 3, 6, 10]long_arr 数组倒数第 2 位元素。

  • sums[-1] - sums[0] = 10 - 1 = 9

可以直接通过 sums 两个和相减得出答案,再来看看求其他元素:

  • long_arr 倒数第 3 位: sums[-1] - sums[1] = 10 - 3 = 7
  • long_arr 正数第 2 位: sums[1] - sums[0] = 3 - 1 = 2

所以,有了这样一个前缀和,就相当于拥有了一个矩阵,没有理解这个相减逻辑,没关系看图就能明白了。

  • 看 0 层(用 i 来表示当前层数,即 i=0),10 - 0 = 10,所以下一层(i = 1)的这个位置还是 10
  • 看 1 层,10 - 1 = 9,所以下一层(i = 2)的这个位置就是 9

可以看到,每个元素和该元素所在层的第一个元素相减,就是下一层的该位置的值

每遍历一层就会少一个元素,顺着层数的增加,每一层的第一个元素都在后移。

每一层的第一个元素的位置是和层数相匹配的,看图:

  • 第 0 层,第一个元素的坐标就是 (0, 0)
  • 第 1 层,第一个元素的坐标就是 (1, 0)
  • 第 2 层,第一个元素的坐标就是 (2, 0)


回到题目,还记得上面讲找一个矩阵的前 K 个元素之和吗?

这是一个矩阵,通过一个值,筛出矩阵的前 K 个数,类似于 378. 有序矩阵中第 K 小的元素 这道题。

寻找第 K 个数

通过二分查找猜出一个数,这个数就是第 K 个元素的值

再次提醒,通过二分找到的这个元素,表示的是第 K 个元素的值。 不然写了半天,不知道为什么写二分查找,找出来是什么东西。对,说的就是我。

已知目标数 K(表示有 K 个数),猜一个数 x,找出矩阵中小于等于 x 的总数 count

查找范围是 [0, preSums[n]]preSums 就是原数组的前缀和,preSums[n] 就是矩阵的右上角,是该矩阵中最大的数,例如下图中的 10


注意:前缀和下标为 0 的元素一般会用 0 占位,第 0 个元素的前缀和就是 0 ,符合直觉,方便计算。


那么总数怎么求?

总数就是找该矩阵中小于等于 x 的元素的总数。

对于一个真实的矩阵,相信大家应该都会,现在只是一个前缀和。上面讲了前缀和与矩阵的关系,这里就可以用上了。

在每一层遍历时,从左往右每个元素都去减第 1 个元素,差值小于等于 x 就继续右移,直至大于 x 时,表示当前层遍历结束。

我们在遍历每一层时,是通过前缀和的差值来判断是否符合小于等于 x 的,所以每一层的遍历其实是对下一层满足条件的元素个数的统计。

一层遍历结束,就可以计算下一层满足条件的元素个数为 j - i - 1, j 表示纵坐标

比如这里的 x 是 3, 最终不断向右移动会停在 66 - 0 不满足 <= 3,那么下一层满足条件的元素个数就是 3 - 0 - 1 = 2 就是两个,看图下一层(黄色块)确实就是两个数符合,也就是 ij 中间的元素个数(不包含 ij

用代码实现出来就是这样:

def getCount(x: int) -> int:
	count = 0
	j = 1
	for i in range(n):
		while j <= n and prefixSums[j] - prefixSums[i] <= x:
			j += 1
		count += j - i - 1
	return count

现在可以根据一个值来求出矩阵中小于等于该值的元素总个数了。

二分的取值范围:[0, preSums[n]],左闭右闭。

选择 while left <= right 作为循环条件。

接下来比较 countk

  1. 如果 count > k,说明 x 太大了,应该收缩右边界,即 right = mid - 1
  2. 如果 count < k,说明 x 太小了,应该收缩左边界,即 left = mid + 1
  3. 如果 count == k,可能刚好符合,也可能是还有更小的值,所以继续收缩右边界,即 right = mid - 1

所以二分如下:

def getKth(k: int) -> int:
	left, right = 0, prefixSums[n]
	while left <= right:
		mid = (left + right) // 2
		count = getCount(mid)
		if count < k:
			left = mid + 1
		else:
			right = mid - 1
	return left

现在有了第 K 个元素的值,记为 num,接下来就是又遍历矩阵(从 0 层开始,i = 0):

  1. 每一层从左往右遍历,元素(计算方式与 getCount 中的一致)小于 num 则继续向右移动,直到不满足;
  2. 一层遍历结束时,得到纵坐标 j
  3. 记录当前层符合条件的元素个数 j - i

为什么是小于?

这个矩阵的元素是可以重复的,比如 这个数组[1, 2, 2, 3]num = 2, k = 2,如果是小于等于就会找出三个元素 1, 2, 2,明显多出了一个 2

那么这里判断条件是小于,先把小于 2 的元素给加上并记录其数量,最后看看等于 2 的元素还差多少个(diff = 总数量 k - 已记录数量),通过 diff * num = 1 * 2 补上即可。

所以,在每一层遍历结束时,还需记录下当前层符合条件的元素个数,也就是 j - i

到最后所有层遍历完后,已符合条件的元素个数为 record_count,最后再加上 num * (k - record_count 即可。


接下来,是通过前缀和的前缀和来计算前 K 个元素的和了。

还是以 nums = [1, 2, 3, 4] 为例,它的前缀和是 preSums = [1, 3, 6, 10]preSums 的前缀和是 prePreSums = [1, 4, 10, 20]

我们同样把 prePreSums 展开成矩阵来看:

如图所示,我想求 preSums [0, 2] 的和,直接访问 prePreSums[2] 即可。

假如想求下图中绿色块的和,会发现在 prePreSums 中对应位置是 9,而不是 7

  • 9 是怎么来的? prePreSums[3] - prePreSums[1],表示的就是 preSums[2] + preSums[3] = 3 + 6 = 9
  • 25 是怎么来的? preSums[2]- preSums[1] = 3 - 1 = 2preSums[3] - preSums[1] = 6 - 1 = 5,也就是分别减去了所在层的第一个元素。

所以 7 就是通过这个公式计算而来:

prePreSums[3] - prePreSums[1] - (3 - 1) * preSums[1]

  • 3 表示纵坐标,用 j 来表示
  • 1 表示横坐标,用 i 来表示

换成表达式就是:

prePreSums[j] - prePreSums[i] - (j - i) * preSums[i]

至此,整个流程应该算是分析完毕了。


以下代码来源是官方题解,我加了部分注释。

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        MODULO = 10**9 + 7
        prefixSums = [0]
        for i in range(n):
            prefixSums.append(prefixSums[-1] + nums[i])
        
        prefixPrefixSums = [0]
        for i in range(n):
            prefixPrefixSums.append(prefixPrefixSums[-1] + prefixSums[i + 1])

        def getCount(x: int) -> int:
            count = 0
            j = 1
            # 看做是遍历矩阵
            for i in range(n):
	            # i 在不断增长,所以 prefixSums[i] 一直表示都是当前层的第一个元素
                while j <= n and prefixSums[j] - prefixSums[i] <= x:
	                # 符合条件就右移
                    j += 1
                j -= 1
                count += j - i
            return count

        def getKth(k: int) -> int:
	        # 这里整个二分查找就是求左边界
			# 即找到第一个满足 count == k 的值(使count == k的最小值)
            left, right = 0, prefixSums[n]
            while left <= right:
                mid = (left + right) // 2
                count = getCount(mid)
                if count < k:
                    left = mid + 1
                else:
                    right = mid - 1
            return left

        def getSum(k: int) -> int:
            num = getKth(k)
            total, count = 0, 0
            j = 1
            for i in range(n):
                while j <= n and prefixSums[j] - prefixSums[i] < num:
                    j += 1
                # 当前 j 位置的元素是 i 行 第 1 个大于等于 num 的值
                # 我们要找的是最后一个小于 num 的元素,所以 -1
                j -= 1
	            
                total += prefixPrefixSums[j] - prefixPrefixSums[i] - prefixSums[i] * (j - i)
                # 记录当前行符合条件的个数
                count += j - i
	        # 最后补上等于 num 的部分
            total += num * (k - count)
            return total

        return (getSum(right) - getSum(left - 1)) % MODULO

小结

最近在刷二分查找的题,这道题的二分查找对我来说,真的是绕了。

刚开始看题解的时候,真的是看不进去,所以画一画图方便理解。

希望这篇题解能够帮助到你,如有纰漏欢迎指正。

2

评论区