难度: Hard
一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。
给你一个整数数组 nums ，返回 nums 的所有非空 子序列 的 宽度之和 。由于答案可能非常大，请返回对 109 + 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 <= 1051 <= nums[i] <= 105运行时间: 152 ms
内存: 25.7 MB
class Solution:
def sumSubseqWidths(self, nums: List[int]) -> int:
MOD = 10 ** 9 + 7
nums.sort()
ans, pow2 = 0, 1
for x, y in zip(nums, reversed(nums)):
ans += (x - y) * pow2
pow2 = pow2 * 2 % MOD
return ans % MOD
该题解首先对数组进行排序。排序后，对于排序数组中的任意两个元素x和y，如果x位于y之前，则在所有包含x和y的子序列中，x总是最小值，y总是最大值。利用这一特点，题解通过遍历排序后的数组来计算所有可能的子序列的宽度之和。具体实现中，题解使用zip函数将排序数组与其翻转后的自身进行配对，配对后的元组(x, y)中x总是小于等于y。每个配对元组对应的贡献是(x - y)乘以当前的2的幂次，这是因为数组中任一元素在子序列中出现的次数等于2的幂次（即该元素可以出现或不出现，有两种情况）。题解中用pow2变量来追踪2的幂次，每次迭代后都会更新这个值。最终结果对一个大数进行模运算，以防止溢出。
时间复杂度: O(n log n)
空间复杂度: O(1)
# 定义解决问题的类
class Solution:
def sumSubseqWidths(self, nums: List[int]) -> int:
MOD = 10 ** 9 + 7 # 定义模数防止溢出
nums.sort() # 对输入数组排序
ans, pow2 = 0, 1 # 初始化结果和2的幂次
for x, y in zip(nums, reversed(nums)): # 遍历数组和其反向数组的元素
ans += (x - y) * pow2 # 计算每对元素贡献的宽度和
pow2 = pow2 * 2 % MOD # 更新2的幂次并取模
return ans % MOD # 返回结果取模
在计算宽度之和时，排序的目的是为了方便确定任意两个元素在所有可能的子序列中的最小值和最大值的关系。排序后，对于任意两个元素x和y，如果x位于y之前（即x的索引小于y的索引），那么在所有包含x和y的子序列中，x总是最小值，y总是最大值。这种排序确保了在遍历和计算时，能够直接通过位置关系来判断元素的大小，简化了问题的复杂度。
`pow2`变量表示2的幂次，用于计算每对元素(x, y)在所有子序列中的贡献次数。每个元素在子序列中出现的次数等于2的幂次，因为每个元素可以出现或不出现，有两种选择。使用`pow2 * 2 % MOD`更新是为了在每一步中计算下一个2的幂次，同时使用模运算防止数值过大导致整数溢出，保证计算结果的稳定性和准确性。
使用`zip(nums, reversed(nums))`的意义在于直接获取排序后数组中位置对称的元素对，以便计算从数组两端到中心的每对元素的贡献。这样配对意味着对于数组中的每个元素，它在配对中一次作为最小值（与之后的元素配对），一次作为最大值（与之前的元素配对）。这种配对方式，使得计算宽度和时，可以有效地通过每对元素的差（x - y）乘以它们在子序列中的出现次数，来累加所有可能的子序列宽度。
此处使用`(x - y) * pow2`的表达式是因为在`zip(nums, reversed(nums))`的配对中，第一个元素x总是从排序后的数组取，而第二个元素y是从数组的反向（即从大到小）取。因此，在每对配对中，x实际上是小于等于y的。这里使用x - y而不是y - x是因为在配对的表达式中，配对元素的顺序已经确保了x是较小的值，所以直接计算x - y可以得到负值或零，这符合求宽度（最大值减最小值）的目的。