未排序数组中累加和小于或等于给定值的最长子数组长度

描述：

给定一个无序数组arr，其中元素可正、可负、可0。给定一个整数k，求arr所有的子数组中累加和小于或等于k的最长子数组长度 例如：arr = [3, -2, -4, 0, 6], k = -2. 相加和小于等于-2的最长子数组为{3, -2, -4, 0}，所以结果返回4

[要求] 时间复杂度为O(n)，空间复杂度为O(n)

输入描述:

第一行两个整数N, k。N表示数组长度，k的定义已在题目描述中给出
第二行N个整数表示数组内的数

输出描述:

输出一个整数表示答案

示例1

输入

5 -2
3 -2 -4 0 6

输出

4

链接：https://www.nowcoder.com/questionTerminal/3473e545d6924077a4f7cbc850408ade
来源：牛客网

解析：

LeetCode中有关于求和的题目，具体分析汇总参见我之前的文章 LeetCode中关于求和的汇总，这里的不同之处在于要求的是小于等于K的，没法像之前那样采用hashmap空间换时间将sum-k存放起来。本题我们要存的是值要大于sum-k，它是一个不定值，我们需要遍历查找，时间复杂度达到O(N)，整体达到O(N*N)。如何能达到时间复杂度(N*logN)呢？看到logN我们直接想到的就是二分，使用二分的前提条件是有序。

思路：

我们需要一个辅助数组h（进行保存的时候保存的是某位置前面的累加和的最大值），显然这个数组是非递减的，我们就可以使用二分来查找。我们遍历原数组，在h数组中查找第一个大于或等于sum-k的数的位置，这个位置到当前位置元素的累加和一定是小于或等于k的当前最长子数组，也就是说当前子数组的值为sum，找到的位置前面累加是大于或等于sum-k的，后面的累加和就是小于或等于k的，也就是我们要的部分，然后看看这个长度是否是当前最长的，若是就记录下来，若不是继续遍历。整个过程我们遍历了一遍，查找用二分，整体时间复杂度为(N*logN)。

代码如下：

int getid(vector<int> & res, int x){
    int low = 0, hight = res.size() - 1, mid = 0, ans = -1;
    while (hight >= low){
        mid = (low + hight) / 2;
        if (res[mid] >= x){
            ans = mid;
            hight = mid - 1;
        }
        else
            low = mid + 1;
    }
    return ans;
}
int getlen(vector<int> & res, int x){
    vector<int>h(res.size() + 1, 0);
    int sum = 0;
    h[0] = sum;
    for (int i = 0; i < res.size(); i++){
        sum += res[i];
        h[i + 1] = max(h[i], sum);
    }
    sum = 0;
    int ans = 0, pre = 0, len = 0;
    for (int i = 0; i < res.size(); i++){
        sum += res[i];
        pre = getid(h, sum - x);
        len = pre == -1 ? 0 : i - pre + 1;
        ans = max(ans, len);
    }
    return ans;
}
int main()
{
    int n,x;
    cin>>n>>x;
    vector<int>res(n);
    for(int i=0;i<n;i++)
        cin>>res[i];
    cout<<getlen(res,x)<<endl;
    return 0;
}

参考：https://blog.csdn.net/qq_31010431/article/details/52237544

https://www.nowcoder.com/questionTerminal/3473e545d6924077a4f7cbc850408ade