LeetCode_数学推导_困难_891.子序列宽度之和

╰半橙微兮° 2023-10-07 21:14 3阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

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

给你一个整数数组 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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/sum-of-subsequence-widths

## 2.思路 ##

（1）数学推导  
思路参考[该 LeetCode 用户题解][LeetCode]。

① 假如数组 nums = \[2, 1, 3\]，并且我们可以知道**子序列顺序不会对结果产生影响**；

② 比如其子序列有 \[1\], \[2\], \[3\], \[2,1\], \[2,3\], \[1,3\], \[2,1,3\]，这与 nums = \[1,2,3\] 的子序列 \[1\],\[2\],\[3\],\[1,2\],\[1,3\],\[2,3\],\[1,2,3\] 的最终结果是一样的；

③ 所以我们按照**递增排序**后讨论，这样每个元素都比它左边大或相等（作为最大值），比它右边小（作为最小值）；

④ 那么我们**只需要讨论每个元素左右的贡献值**，这里拿数字 2 作为例子，那么它作为最大值贡献了 2i 次（i = 1，排序后），作为最小值贡献了 2(n-i-1) 次，注：贡献都包含本身统计，结果相减没影响。那么最终结果就是每个数贡献值相加 sum(2i \- 2^(n - i - 1)^) \* nums\[i\])；

## 3.代码实现（Java） ##

//思路1————数学推导
    class Solution {
        
        public int sumSubseqWidths(int[] nums) {
        
            Arrays.sort(nums);
            int mod = (int) 1e9 + 7;
            int length = nums.length;
            long result = 0;
            long[] pow = new long[length];
            pow[0] = 1;
            //初始化2^n的值
            for (int i = 1; i < length; i++) {
        
                pow[i] = (pow[i - 1] << 1) % mod; 
            }
            //计算总和
            for (int i = 0; i < length; i++)
                result = (result + (pow[i] - pow[n-i-1]) * nums[i] % mod) % mod;       
            return (int) result;
        }
    }

[LeetCode]: https://leetcode.cn/problems/sum-of-subsequence-widths/solution/by-muse-77-f6s5/