LeetCode-891. 子序列宽度之和【排序，数学，数组】

题目描述：

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

给你一个整数数组 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 <= 10^5
1 <= nums[i] <= 10^5
https://leetcode.cn/problems/sum-of-subsequence-widths/description/

解题思路一：排序与数学，排序之后看每个nums[i]的贡献。

假设排序后nusm[i]左边有left个元素，右边有right个元素，那么这个元素作为最小值出现的子序列一共有2^right个（右边的每个元素可以选取或不选取）；而作为最大值出现的子序列一共有2^left个。（同理）
作为最小值贡献是负数，作为最大值贡献是正数。
因此，元素A[i]对最后的总和的贡献就等于：
$$(2^{left}-2^{right})\ast nums[i]=(2^i-2^{n-i-1})\ast nums[i]$$

代码如下：

const long long MOD=1e9+7;
class Solution {
public:
    int sumSubseqWidths(vector<int>& nums) {
        long long n=nums.size(),ans=0;
        sort(nums.begin(),nums.end());//排序
        vector<long long> two(n+1);
        two[0]=1;
        for(int i=1;i<=n;++i) two[i]=(two[i-1]<<1)%MOD;//计算2的各个幂次的值
        for(int i=0;i<n;++i){//对于每个nums[i]计算一次贡献。
            int left=i,right=n-i-1;
            ans=(ans+(two[left]-two[right])*nums[i])%MOD;
        }
        return (ans+MOD)%MOD;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度：O(nlogn)排序
空间复杂度：O(n)

解题思路二：优化1

class Solution {
    const int MOD=1e9+7;
public:
    int sumSubseqWidths(vector<int>& nums) { 
        sort(nums.begin(),nums.end());       
        int n=nums.size(),pow2[n];
        long ans=0L;       
        pow2[0]=1;
        for(int i=1;i<n;++i) pow2[i]=pow2[i-1]*2%MOD;//先乘法再取模
        for(int i=0;i<n;++i) ans+=long(pow2[i]-pow2[n-i-1])*nums[i];//在题目的数据范围下，这不会溢出
        return (ans%MOD+MOD)%MOD;//注意上面有减法ans可能为负数
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度：O(nlogn)排序
空间复杂度：O(n)

解题思路三：还有一种思路是计算 2ⁱ 对答案的贡献，优化空间！

即：
$$(\text{nums}[i]-\text{nums}[n-1-i])\times 2^i$$

class Solution {
    const int MOD = 1e9 + 7;
public:
    int sumSubseqWidths(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        long ans = 0L, pow2 = 1L;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            ans += (nums[i] - nums[n - 1 - i]) * pow2; // 在题目的数据范围下，这不会溢出
            pow2 = pow2 * 2 % MOD;
        }
        return (ans % MOD + MOD) % MOD; // 注意上面有减法，ans 可能为负数
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度：O(nlogn)排序
空间复杂度：O(1)

参考链接：
111