子序列宽度之和Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。
给你一个整数数组 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 <= 105
- 1 <= nums[i] <= 105
# 思路
# 解法
class Solution {
final int MOD = 1000000007;
public int sumSubseqWidths(int[] nums) {
// 贡献度 + 排序
// 排序后以nums[i]为最大值的子序列有max = 2^i个，
// 以nums[i]为最小值的子序列有min = 2^(n-1-i)个。
// 原理：以max为例，构成以nums[i]为最大值的子序列所选数字必定是排序后在i及i之前的，
// 该段子数组中每个数有选或不选两种方案，从排序后的nums[0]累乘到nums[i]，
// 共2^i种方案，也就是共有2^i个以nums[i]为最大值的子序列。
// nums[i]对ans的的贡献度即其作为(最大值的次数-作为最小值的次数)*nums[i]。
// 累加过程相当于将nums每个子序列中(最大值-最小值)的捉对计算，分化转移到每个数字。
// 注意int溢出，ans计算过程中使用long类型，且因为取模计算过程中存在减法，
// 所以对ans取模+MOD后再取模恢复正常。
int n = nums.length;
Arrays.sort(nums);
int[] pow = new int[n];
pow[0] = 1;
for(int i = 1; i < n; ++i){
pow[i] = pow[i-1] * 2 % MOD;
}
var ans = 0L;
for(int i = 0; i < n; ++i){
ans += (long)nums[i] * (pow[i] - pow[n-i-1]) % MOD;
}
// 取模过程中存在减法，ans可能为负，所以对ans取模+MOD后再取模恢复正常。
return (int)(ans % MOD + MOD) % MOD;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 总结
- 分析出几种情况，然后分别对各个情况实现
