0891._Sum_of_Subsequence_Widths.md

891. Sum of Subsequence Widths

难度: Hard

刷题内容

原题连接

• https://leetcode.com/problems/sum-of-subsequence-widths/description/

内容描述

Given an array of integers A, consider all non-empty subsequences of A.

For any sequence S, let the width of S be the difference between the maximum and minimum element of S.

Return the sum of the widths of all subsequences of A. 

As the answer may be very large, return the answer modulo 10^9 + 7.

 

Example 1:

Input: [2,1,3]
Output: 6
Explanation:
Subsequences are [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3].
The corresponding widths are 0, 0, 0, 1, 1, 2, 2.
The sum of these widths is 6.
 

Note:

1 <= A.length <= 20000
1 <= A[i] <= 20000

解题方案

思路 1 - 时间复杂度: O(NlgN)- 空间复杂度: O(N)******

设n为A数组的长度

先给A排序，其中以A[0]为最小值的子序列的个数为2^(n-1)，以A[0]为最大值的子序列的个数为2^(0)，以此类推。

开始写的代码如下：

class Solution(object):
    def sumSubseqWidths(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        A.sort()
        res, n = 0, len(A)
        for i in range(len(A)):
            res -= A[i] * pow(2, n-1-i)
            res += A[i] * pow(2, i)
            res %= pow(10, 9) + 7
        return res

但是一直超时，于是我觉得是因为pow()函数太费时间了，所以用空间换时间，先把所有2的0到(n-1)次方全部存起来，然后后面直接取就行了，果然AC

beats 84.15%

class Solution(object):
    def sumSubseqWidths(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        MOD = 10**9 + 7
        res, n = 0, len(A)
        A.sort()

        pow2 = [1]
        for i in xrange(1, n):
            pow2.append(pow2[-1] * 2 % MOD)

        for i, x in enumerate(A):
            res -= x * pow2[n-1-i] % MOD
            res += x * pow2[i] % MOD
        return res % MOD