K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
已知存在一个长度为10^5的正整数数组arr，需要求解其中最长的连续子数组，使得该子数组的元素和不超过给定值K。原始暴力枚举所有区间左端点并逐个扩展右端点的做法时间复杂度为O(n²)，本题中数组所有元素均为正整数。
使用前缀和数组结合二分查找，为每个左端点快速找到最大的合法右端点
使用双指针（滑动窗口）维护合法区间，左右指针仅单向遍历数组
使用递归分治的方法，将数组划分为左右两部分分别求解后合并结果
使用哈希表存储前缀和出现的位置，快速查询符合条件的区间端点