题解丨字节跳动试题：第k大的子数组

给定一个长度为n的数组a，它有n(n+1)/2??个子数组。请计算这些子数组的和，然后按照升序排列，并返回排序后第k个数。

• 1≤n≤10?^5
• 1≤a?i≤10^?9
• 1≤k≤?n(n+1)/2

在线评测地址：点击此处前往

Example1

Input: 
[2,3,1,4]
6
Output:5
Explanation:
我们可以得到所有子数组的和是 [1,2,3,4,4(3 + 1), 5(1 + 4), 5(2 + 3), 6(2 + 3 + 1), 8(3 + 1 + 4), 10(2 + 3 + 1 + 4)]。其中第六个是5。