LeetCode 891 子序列宽度之和

2018-08-20

写在前面：

感谢情郎捞了我一把，LeetCode周赛在这道题卡了很久

题目：

给定一个整数数组 A ，考虑 A 的所有非空子序列。

对于任意序列 S ，设 S 的宽度是 S 的最大元素和最小元素的差。

返回 A 的所有子序列的宽度之和。

由于答案可能非常大，请返回答案模 10^9+7。

示例：

输入：[2,1,3]
输出：6
解释：
子序列为 [1]，[2]，[3]，[2,1]，[2,3]，[1,3]，[2,1,3] 。
相应的宽度是 0，0，0，1，1，2，2 。
这些宽度之和是 6 。

提示：

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

解题思路：

对于一个序列（a, $c_1$, $c_2$, …, $c_n$, b），a、b分别为该序列的最小值和最大值。那么以 a、b 为最小值和最大值的子序列有 $2^n$ 种情况。

因此，我们需要先对 A 进行排序，再依次选取 A[j]、A[i] 作为其最大值和最小值，那么这两者对应的子序列宽度之和为$(A[j] - A[i]) * 2^{(j - i - 1)}$

又有模的运算规则：

(a + b) % p = (a % p + b % p) % p

因此对应代码有：

sort(A.begin(), A.end());
int n = A.size();
vector<long> base;
long b = 1;
for (int i = 0; i < n; i++) {
    base.push_back(b);
    b = (2 * b) % mod;
}
for (int i = 0; i < A.size() - 1; i++) {
    for (int j = 1; i + j < A.size(); j++) {
        width = (width + ((A[i + j] - A[i]) * base[j - 1]) % mod) % mod;
    }
}

base数组需要声明为long或者long long类型。刚开始的时候，声明为int类型，当测试样例非常大之后，一直过不去。后来发现是(A[i + j] - A[i]) * base[j - 1])的结果过大，超过int的范围，因此后面的运算自然就错了。

但是这样子的代码还不行，会有超时问题，因此我们需要降低复杂度。

原来的计算公式为 $\sum_{i = 0}^{n - 2} \sum_{j = i+ 1}^{n - 1} (A[j] - A[i]) * 2^{j - i - 1}$

我们将其拆解为两个部分 $\sum_{i = 0}^{n - 2} \sum_{j = i+ 1}^{n - 1} A[j] 2^{j - i - 1}$ 和 $\sum_{i = 0}^{n - 2} \sum_{j = i+ 1}^{n - 1} A[i] 2^{j - i - 1}$

当 i 为	$\sum_{i = 0}^{n - 2} \sum_{j = i+ 1}^{n - 1} A[i] * 2^{j - i - 1}$	$\sum_{i = 0}^{n - 2} \sum_{j = i+ 1}^{n - 1} A[j] * 2^{j - i - 1}$
0	$2^0A[0] + 2^1A[0] + … + 2^{n - 2}A[0]$	$2^0A[1] + 2^1A[2] + … + 2^{n - 2}A[n - 1]$
1	$2^0A[1] + 2^1A[1] + … + 2^{n - 3}A[1]$	$2^0A[2] + 2^1A[3] + … + 2^{n - 3}A[n - 1]$
2	$2^0A[0] + 2^1A[0] + … + 2^{n - 4}A[2]$	$2^0A[3] + 2^1A[4] + … + 2^{n - 4}A[n - 1]$
…	…	…
n-2	$2^0A[n - 2]$	$2^0A[n - 1]$

进一步化简有：
$\sum_{i = 0}^{n - 2} \sum_{j = i+ 1}^{n - 1} A[i] 2^{j - i - 1} = (2^{n - 1} - 1)A[0] + (2^{n - 2} - 1)A[1] + … + (2^{1} - 1)A[n - 2]$
$\sum_{i = 0}^{n - 2} \sum_{j = i+ 1}^{n - 1} A[j] 2^{j - i - 1} = (2^{n - 1} - 1)A[n - 1] + (2^{n - 2} - 1)A[n - 2] + … + (2^{1} - 1)A[1]$

是以，两者之差 = $(2^{n - 1} - 1)(A[n - 1] - A[0]) + (2^{n - 2} - 1)(A[n - 2] - A[1]) + … + (2^{1} - 1)(A[1] - A[n - 2])$

所以代码为：

class Solution {
public:
    int sumSubseqWidths(vector<int>& A) {
        int width = 0;
        int mod = 1e9 + 7;
        sort(A.begin(), A.end());
        vector<long> base;
        long b = 1;
        int n = A.size();
        for (int i = 0; i < n; i++) {
            base.push_back(b);
            b = (2 * b) % mod;
        }
        /*
        for (int i = 0; i < A.size() - 1; i++) {
            for (int j = 1; i + j < A.size(); j++) {
                width = (width + ((A[i + j] - A[i]) * base[j - 1]) % mod) % mod;
            }
        }*/
        for (int i = 0; i < n - 1; i++) {
            long long temp = ((A[n - 1 - i] - A[i]) * (base[n - 1 - i] - 1)) % mod;
            if (temp < 0) temp += mod;
            width = (width + temp) % mod;
        }
        return width;
    }
};