demo

1 -> 0 1, 2 -> 1 1, 2, 3 -> （多出4中组合，1 和 2 选或者不选）

多出的结果：（1， 3） （2， 3）（1，2， 3） 总和为 2 + 1 + 2 = 5 可看出选择 1 时的数目，取决于 1 到 3 之前的数目，取其 2 的幂数。（此种情况下， 2 1 = 2） 可得： 2 1 = 2 2 * （3 - 1） = 4
2 ** 0 = 1 1 * （3 - 2） = 1

目标

假设有 1，2 ，3， 4 的数据，如何一次循环后，找出不同的子序列的 “宽度”（最大值 - 最小值）

1，2 -> ( w1 -> 1) 1, 2, 3 -> (w1 -> 1 w2 -> 2) 1, 2, 3, 5 -> (w2 ->1 w3 -> 2 w4 -> 4) 1，2，3， 5， 8 -> (w3 -> 1 w5-> 2 w6 -> 4 w7 -> 8) 如何在一次循环中找出这些不同的宽度值。

思路

通过集合记录上次的值。 循环遍历排序后的数组，当新加入一个数后，计算其与前一个所得的差值，根据此差值更新当前集合中的宽度及数值

参考 力扣 只考虑当前的元素，计算其对结果的影响。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        A.sort()
        ans = 0
        N = len(A)
        map2 = [1]
        for i in range(1, N):
            map2.append(map2[i - 1] * 2)
        for i in range(N):
            left = map2[i]
            right = map2[N - i - 1]
            ans += (left - right) * A[i]
        return ans % (10 ** 9 + 7)