一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。
给你一个整数数组 nums ，返回 nums 的所有非空 子序列 的 宽度之和
由于答案可能非常大，请返回对 109 + 7 取余 后的结果。
子序列 定义为从一个数组里删除一些（或者不删除）元素，
但不改变剩下元素的顺序得到的数组
例如，[3,6,2,7] 就是数组 [0,3,1,6,2,2,7] 的一个子序列。
输入：nums = [2,1,3]。
输出：6。
解题思路：
- 排序
首先对数组进行排序，这样我们就可以根据每个子序列的首尾元素来计算它的宽度了。
- 计算宽度
我们使用 A 表示当前子序列的宽度，即末尾元素与首元素的差值，使用 B 表示上一个子序列的宽度，即前一次循环中的 A 值。具体计算过程如下：
A = (D * nums[i]) % mod
B = ((B * 2) % mod + nums[i - 1]) % mod
ans = (ans + A - B + mod) % mod
C = (C * 2) % mod
D = (D + C) % mod其中 D 和 C 分别表示当前子序列的长度和可能的贡献值，计算方法如下：
C = (C * 2) % mod
D = (D + C) % mod- 取模
由于答案非常大，需要对其进行 10^9+7 取模，即将 ans 的值对 mod 取余。
时间复杂度：
排序的时间复杂度为 O(nlogn)，计算宽度的时间复杂度为 O(n)，因此总的时间复杂度为 O(nlogn)。
空间复杂度：
除了输入数据外，算法使用了常数级别的额外空间，因此空间复杂度为 O(1)。
go完整代码如下：
package main
import (
"fmt"
"sort"
)
func sumSubseqWidths(nums []int) int {
sort.Ints(nums)
mod := 1000000007
ans := 0
var A, B, C, D int64 = 0, 0, 1, 1
for i := 1; i < len(nums); i++ {
A = (D * int64(nums[i])) % int64(mod)
B = ((B*2)%int64(mod) + int64(nums[i-1])) % int64(mod)
ans = (ans + int(A-B+int64(mod))) % int(mod)
C = (C * 2) % int64(mod)
D = (D + C) % int64(mod)
}
return ans
}
func main() {
nums := []int{2, 1, 3}
result := sumSubseqWidths(nums)
fmt.Println(result)
}
rust完整代码如下：
fn sum_subseq_widths(nums: Vec<i32>) -> i32 {
let mut nums = nums.clone();
nums.sort_unstable();
let mod_num = 1000000007;
let mut ans = 0;
let mut a = 0;
let mut b = 0;
let mut c = 1;
let mut d = 1;
for i in 1..nums.len() {
a = (d * nums[i] as i64) % mod_num;
b = ((b * 2) % mod_num + nums[i - 1] as i64) % mod_num;
ans = (ans + a - b + mod_num) % mod_num;
c = (c * 2) % mod_num;
d = (d + c) % mod_num;
}
ans as i32
}
fn main() {
let nums = vec![2, 1, 3];
let result = sum_subseq_widths(nums);
println!("{}", result);
}
c完整代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007
int compare(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
int sumSubseqWidths(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), compare);
long ans = 0, A = 0, B = 0, C = 1, D = C;
for (int i = 1; i < numsSize; i++) {
A = (D * nums[i]) % MOD;
B = ((B * 2) % MOD + nums[i - 1]) % MOD;
ans = (ans + A - B + MOD) % MOD;
C = (C * 2) % MOD;
D = (D + C) % MOD;
}
return (int)ans;
}
int main() {
int nums[] = { 2, 1, 3 };
int numsSize = sizeof(nums) / sizeof(nums[0]);
int result = sumSubseqWidths(nums, numsSize);
printf("%d\n", result);
return 0;
}
c++完整代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int sumSubseqWidths(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int mod = 1000000007;
long ans = 0, A = 0, B = 0, C = 1, D = C;
for (int i = 1; i < nums.size(); i++) {
A = (D * nums[i]) % mod;
B = ((B * 2) % mod + nums[i - 1]) % mod;
ans = (ans + A - B + mod) % mod;
C = (C * 2) % mod;
D = (D + C) % mod;
}
return static_cast<int>(ans);
}
int main() {
vector<int> nums{ 2, 1, 3 };
int result = sumSubseqWidths(nums);
cout << result << endl; // 输出：6
return 0;
}
