# LintCode领扣 题解丨字节跳动面试题：第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:

【题解】

k大的子区间，而我们的区间总个数共有n(n+1)/2个，当n为10^5​​时这个数高达10^10级别。我们显然不能暴力的枚举每一个区间和然后排序。

O(nlog(n))

public class Solution {

/**
* @param a: an array
* @param k: the kth
* @return: return the kth subarray
*/

private int check(long x, int[] a, long k) {
long tmp1 = 0, tmp2 = 0, now = a[0];
int l = -1, r = 0, n = a.length;
long all = (long)n * (n + 1) / 2;
while (l <= r && r < n)
{
if (now >= x) {
if (now == x) {
tmp2++;
} else {
tmp1++;
}
tmp1 += n - r - 1;
l++; now -= a[l];
}
else {r++; if (r < n) now += a[r];}
}
if (all - tmp1 - tmp2 < k && all - tmp1 >= k) return 0;
if (all - tmp1 - tmp2 >= k) return 1;
else return -1;
}
public long thekthSubarray(int[] a, long k) {
int n = a.length;
long sum = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
}
long l = 1, r = sum;
while (l <= r) {
long mid = (l + r) / 2;
int flag = check(mid, a, k);
if (flag == 0) {
return mid;
}
if (flag == 1) {
r = mid - 1;
}
else {
l = mid + 1;
}
}
return -1;
}

+ 订阅