What is the main pattern used in Sum of Subsequence Widths?

The pattern combines array sorting with combinatorial math to calculate each element's contribution as maximum and minimum efficiently.

Why do we sort the array before calculating subsequence widths?

Sorting ensures we can systematically identify which elements act as maxima and minima in subsequences, enabling combinatorial counting without full enumeration.

How is modulo 10^9 + 7 applied in this problem?

All cumulative sums are taken modulo 10^9 + 7 to prevent integer overflow from the potentially large total of subsequence widths.

Can we compute subsequence widths without combinatorial math?

Brute-force enumeration is possible but impractical; combinatorial math allows O(N log N) performance by counting contributions without generating all subsequences.

What is the time complexity for solving Sum of Subsequence Widths?

Sorting takes O(N log N), and contribution calculations take O(N), so overall time complexity is O(N log N) with O(N) extra space for powers of two.

#891

Hard

auto_awesome数组·数学

LeetCode 题解工作台

子序列宽度之和

一个序列的宽度定义为该序列中最大元素和最小元素的差值。给你一个整数数组 nums ，返回 nums 的所有非空子序列的宽度之和。由于答案可能非常大，请返回对 10 9 + 7 取余后的结果。子序列定义为从一个数组里删除一些（或者不删除）元素，但不改变剩下元素的顺序得到的数组。例如…

数组数学排序

题目描述

一个序列的宽度定义为该序列中最大元素和最小元素的差值。

给你一个整数数组 nums ，返回 nums 的所有非空 子序列 的 宽度之和 。由于答案可能非常大，请返回对 10⁹ + 7 取余后的结果。

子序列 定义为从一个数组里删除一些（或者不删除）元素，但不改变剩下元素的顺序得到的数组。例如，[3,6,2,7] 就是数组 [0,3,1,6,2,2,7] 的一个子序列。

示例 1：

输入：nums = [2,1,3]
输出：6
解释：子序列为 [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 。
相应的宽度是 0, 0, 0, 1, 1, 2, 2 。
宽度之和是 6 。

示例 2：

输入：nums = [2]
输出：0

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

lightbulb

解题思路

方法一：排序 + 枚举元素计算贡献

题目求解的是数组 nums 中所有子序列中最大值与最小值差值之和，注意到“子序列”，并且涉及到“最大值”与“最小值”，我们考虑先对数组 nums 进行排序。

然后我们枚举数组 nums 中的每个元素 $nums[i]$ ，该元素左侧的元素个数为 $i$ ，右侧的元素个数为 $n-i-1$ 。

如果我们将元素 $nums[i]$ 作为子序列的最大值，总共有多少个满足条件的子序列呢？显然，子序列的其他元素应该从左侧的 $i$ 个元素中选取，每个元素有两种选择，即选或不选，因此总共有 $2^i$ 个子序列。同理，如果我们将元素 $nums[i]$ 作为子序列的最小值，那么总共有 $2^{n-i-1}$ 个满足条件的子序列。因此 $nums[i]$ 对答案的贡献为：

\begin{aligned} nums[i] \times (2^i - 2^{n-i-1}) \end{aligned}

我们将数组 nums 中所有元素的贡献累加，即为答案：

\begin{aligned} \sum_{i=0}^{n-1} nums[i] \times (2^i - 2^{n-i-1}) \end{aligned}

我们将上式展开，可以得到：

\begin{aligned} nums[0] \times (2^0 - 2^{n-1}) + nums[1] \times (2^1 - 2^{n-2}) + ... + nums[n-1] \times (2^{n-1} - 2^0) \end{aligned}

再将式子中相同的幂次项合并，可以得到：

\begin{aligned} (nums[0] - nums[n-1]) \times 2^0 + (nums[1] - nums[n-2]) \times 2^1 + ... + (nums[n-1] - nums[0]) \times 2^{n-1} \end{aligned}

即：

\begin{aligned} \sum_{i=0}^{n-1} (nums[i] - nums[n-i-1]) \times 2^i \end{aligned}

因此我们只需要对数组 nums 进行排序，然后计算上述的贡献即可。注意答案的取模操作。

时间复杂度 $O(n\times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组 nums 的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def sumSubseqWidths(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        nums.sort()
        ans, p = 0, 1
        for i, v in enumerate(nums):
            ans = (ans + (v - nums[-i - 1]) * p) % mod
            p = (p << 1) % mod
        return ans

speed

复杂度分析

指标	值
时间	O(N \log N)
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate recognizes the impact of sorting to simplify max/min handling.
question_mark
Look for combinatorial reasoning using powers of two rather than brute-force subsequence enumeration.
question_mark
Notice if modulo arithmetic is applied correctly to avoid overflow issues.

warning

常见陷阱

外企场景

error
Attempting to generate all subsequences leads to exponential time complexity.
error
Ignoring modulo 10^9 + 7 can cause integer overflow for large arrays.
error
Miscounting contributions as max or min without considering array order after sorting.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute sum of widths for subsequences restricted to size k instead of all sizes.
arrow_right_alt
Handle arrays with negative integers and compute subsequence width sums modulo a different prime.
arrow_right_alt
Find subsequences where the width falls within a specific range and sum only those widths.

help

常见问题

外企场景

继续练习

#910 最小差值 II #939 最小面积矩形 #973 最接近原点的 K 个点