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

给你一个整数数组 nums ，返回 nums 的所有非空 子序列 的 宽度之和

由于答案可能非常大，请返回对 109 + 7 取余 后的结果。

子序列 定义为从一个数组里删除一些（或者不删除）元素，

但不改变剩下元素的顺序得到的数组

例如，3,6,2,7 就是数组 0,3,1,6,2,2,7 的一个子序列。

输入：nums = 2,1,3。

输出：6。

答案2023-04-29：

解题思路：

1. 排序

首先对数组进行排序，这样我们就可以根据每个子序列的首尾元素来计算它的宽度了。

1. 计算宽度

我们使用 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

1. 取模

由于答案非常大，需要对其进行 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: Veci32>
    ) ->
 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(vectorint>
    &
 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_castint>
    (ans);

}


int main() {
    
    vectorint>
 nums{
 2, 1, 3 }
    ;
    
    int result = sumSubseqWidths(nums);
    
    cout  result  endl;
     // 输出：6
    return 0;

}
    

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！