给定一个无序数组arr, 其中元素可正, 可负, 可0, 给定一个整数k. 求arr所有的子数组中累加和小于或等于k的最长子数组长度.
例如:
arr[] = {3, -2, -4, 0, 6}, k=2
相加和小于或等于-2的最长子数组为[3, -2, -4, 0],所有结果返回4.
算法分析
基本思想是, 分别求以数组每个元素结尾的子数组中, 累加和小于或等于k的最长子数组长度, 其中最长的那个子数组的长度就是所求的结果.
关键是如何高效地确定, 以每个元素结尾的, 满足要求的最长子数组长度.
例如如果要求以元素 arr[30]结尾, 累加和小于等于k的最长子数组长度.
- arr[0..30]子数组和为sum(30)
- 如果在0和30之间有某个下标j=10, arr[0..10]子数组和为sum(10)
- 有 sum(30) - sum(10) <= k, 并且10是第一个下标满这个条件
- 那么 arr[11..30]即是以arr[30]结尾的, 子数组和小于等于k的最长子数组.
为了更高效地为寻找以每一个元素结尾的满足条件的最长子数组, 需要生成辅助数组.
该辅助数组为以第一个元素开始到目标元素结尾的子数组的和.
辅助数组的第一个元素为0, 表示子数组为空时, 累加和为0.
举一个栗子, 对于数组 [1, 2, -1, 5, -2]
生成的辅助数组为 [0, 1, 3, 2, 7, 5].
这样的辅助数组使用起来还不够高效, 因为每一次查找时, 我们都要遍历一次这个数组, 找到第一个大于 sum - k的元素的下标. 所以我们对辅助数组做修订.
修订后的辅助数组是 [0, 1, 3, 3, 7, 7]. 做这个变动, 是因为我们需要寻找的, 是最早满足累加和大于或等于sum - k的元素下标, 如果在这个元素后面的累加和比sum - k,可以完全忽略. 这里我们将2变为3, 5变为7, 是为了让这个辅助数组有序, 从而可以用二分查找的方式查找第一个大于等于 sum - k的元素.
实现
class Solution
{
public:
int maxSubarraySumLessOrEqualK(std::vector<int>& nums, int target)
{
if (nums.size() == 0)
{
return 0;
}
std::vector<int> sumArray;
int sum = 0;
int maxLen = 0;
sumArray.push_back(sum);
for (int cur = 0; cur < nums.size(); ++cur)
{
sum += nums[cur];
int start = binarySearch(sumArray, sum - target);
int len = start == -1 ? 0 : cur - start + 1;
maxLen = std::max(maxLen, len);
int toPush = std::max(sum, sumArray.back());
sumArray.push_back(toPush);
}
return maxLen;
}
private:
// find element >= key
int binarySearch(std::vector<int> sumArray, int key)
{
int left = 0;
int right= sumArray.size() - 1;
int mid = -1;
while (left <= right)
{
mid = (right + left) / 2;
if (sumArray[mid] >= key)
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return left < sumArray.size() ? left : -1;
}
};
