K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
已知存在一个长度为n的正整数数组arr,我们需要找出其中所有和大于等于给定目标值target的连续子数组的最小长度。现有多种解法可供选择,以下哪种是符合区间枚举优化思想的最优解法?
暴力枚举所有区间起点i和终点j(i≤j),逐个计算区间和并统计满足条件的最小长度,时间复杂度O(n²)
使用滑动窗口算法,维护左右指针,当当前窗口内元素和小于target时右移右指针扩展窗口,否则左移左指针收缩窗口并更新最小长度,时间复杂度O(n)
使用三重循环,依次枚举起点、终点并遍历区间计算和,时间复杂度O(n³)
先对数组元素进行升序排序,再枚举排序后的元素组合计算满足和的条件,时间复杂度O(n log n)