Readme

2386.Find-the-K-Sum-of-an-Array

这是一道真正的Hard。

第一步：转化为求一个正数数组的第k小序列和。

显然，本题最大sum的序列S就是将数组里所有的正数都取出来，对应的是MaxSum。次大的sum值必然是在这个序列S的基础上减去一个已经存在的正数，或者加上一个还未入队的负数。同理，第k大的sum值也必然是从这个序列S里减去若干个已经存在的正数，或者加上若干个还未入队的负数。因为减去正数等于减去它的绝对值，加上负数也等于减去它的绝对值，所以第k大的sum值，等价于在S（即MaxSum）的基础上减去若干个nums里元素的绝对值。故我们只要在nums的绝对值数组里挑出第k小的序列和即可。

第二步：构造一个正数数组的从小到大所有的序列和。

这里直接说明构造的步骤。空集必然对应最小的序列和，我们单独处理。然后

1. 将{nums[0], 0}放入一个小顶堆中（即优先弹出最小值的优先队列）。
2. 如果从PQ里弹出的是{sum, i}（其中sum必然是某个以nums[i]结尾的子序列之和），那么将{sum-nums[i]+nums[i+1], i+1}和{sum+nums[i+1], i+1}加入PQ中（记做操作1和操作2）
3. PQ里第k-1个弹出的sum就是该正数数组里第k大的序列和

第三步：证明这个构造方法的正确性

首先，我们要证明这个构造方法覆盖了所有的子序列。这个直观上不难理解。我们考虑，如果已经生成了所有以nums[0]，nums[1]，... nums[i-1]结尾的子序列，那么能否通过之前定义的方法，生成所有以nums[i]结尾的子序列呢？假设某个以nums[i]结尾的子序列，它的倒数第二个元素是任意的nums[k]，那么我们必然可以通过一个以nums[k]结尾的子序列做一次操作2，再反复进行操作1，就可以得到。

其次，我们要证明这个构造方法不会产生重复的子序列。这个也显然，对于任意形如{X,X,...,X,nums[k],nums[i]}的序列，如果k+1==i，那么它必然唯一由形如{X,X,...,X,nums[k]}的子序列通过一次操作2得到；如果k+1!=i，那么它必然唯一由形如{X,X,...,X,nums[k],nums[i-1]}的子序列通过一次操作1得到。

最后，我们要证明这个构造方法生成的子序列是按照和递增的。这个证明很简洁。假设某个序列A小于序列B，但是B先从队列里弹出，这可能吗？注意，这意味着B在队列里的时候A一定还没有加入队列里（否则PQ会优先弹出A）。既然A不在队列里，说明A的前驱状态A'（上一段证明了存在唯一的A'）也必然不会在队列里，因为A'是小于A的，A'在队列的话更会比B优先弹出，从而导致将A也被导入队列里。同理证明，A'的前驱序列A''也不会在队列里，A''的前驱序列也不会在队列里... 但是所有的序列都是从{nums[0]}开始的，难道这个序列也从未加入过队列吗？从而引发矛盾。

综上，我们证明了这种构造方法一定会一个不漏、一个也不重复地、按从小到大的顺序弹出所有的子序列之和。显然第k-1个弹出来的就是第k小的子序列之和（考虑空集）。