刷题笔记(7):力扣-209.长度最小的子数组

本题来自 leetcode 题库第 209 题:209.长度最小的子数组。题目要求在给定数组中找到和为指定值且长度最小的子数组,难度中等。

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 \([nums_l, nums_{l+1}, ..., nums_{r-1}, nums_r]\),并返回其长度。如果不存在符合条件的子数组,返回 0 。

  • 示例 1:
    输入:target = 7, nums = [2,3,1,2,4,3]
    输出:2
    解释:子数组 [4,3] 是该条件下的长度最小的子数组。

  • 示例 2:
    输入:target = 4, nums = [1,4,4]
    输出:1

  • 示例 3:
    输入:target = 11, nums = [1,1,1,1,1,1,1,1]
    输出:0

  • 提示:
    1 <= target <= \(10^9\)
    1 <= nums.length <= \(10^5\)
    1 <= nums[i] <= \(10^5\)

  • 进阶:

    如果你已经实现 \(O(n^2)\) 时间复杂度的解法, 请尝试设计一个 \(O(n\log(n))\) 时间复杂度的解法。

题解

解法 1:暴力求解

由于寻找的是连续的子数组,因此只需要对每个子数组的起始下标进行遍历,然后内层遍历所有以该起始下标的子数组,并寻找满足和大于等于 target 的数组记录其长度。最终返回最小长度即可。该方法思路直接,不再赘述。

解法 2:前缀和 + 二分查找

该算法需要额外的数组空间,用以存储输入数组的前 n 项。例如数组 [3, 2, 4, 5] 前 n 项和数组为 [3, 5, 9, 14]。如此一来,类似解法 1 中第一层循环里要寻找以 nums[i] 开头的子串使和为 target,只需要在前 n 项和数组里 i 以后的范围内寻找值为 target + nums[i-1] 的元素即可。具体地,可以证明如下:

对于序列 \(a_1,a_2,\cdots,a_i,\cdots,a_n\),其前 n 项和为 \(S_1, S_2, \cdots, S_i,\cdots, S_n\)。若 \(S_k = a_{i-1} + t\),则有 \(a_i + a_{i+1} + \cdots + a_{k} = S_k - a_{i-1} = t\)。因此序列 \(a_i,\cdots,a_k\) 的和为 \(t\)

根据以上的分析,我们需要在前 n 项和序列里查找目标值,注意到题目设定中输入数组为正整数,则说明前 n 项和序列是单增序列,则可使用二分查找法查找目标值。如此一来,对比方法 1 的时间复杂度就下降了。具体的代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* @param {number} target
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function (target, nums) {
function find(arr, to_find, start, end) {
let mid = Math.floor((start + end) / 2)
while (start <= end) {
if (arr[mid] === to_find || (arr[mid] > to_find && arr[mid - 1] < to_find))
return mid
if (arr[mid] > to_find) end = mid - 1
else start = mid + 1
mid = Math.floor((start + end) / 2)
}
return -1
}

const n_sum = [0]
nums.reduce((pre, cur) => {
const i_sum = pre + cur
n_sum.push(i_sum)
return i_sum
}, 0)


let ans = nums.length + 1
let to_find, end
for (let i = 0; i < nums.length; i++) {
if (nums[i] >= target) return 1
to_find = target + n_sum[i]
end = find(n_sum, to_find, i + 2, Math.min(nums.length, i + ans))
ans = end === -1 ? ans : Math.min(end - i, ans)
}

return ans === nums.length + 1 ? 0 : ans
};

该算法时间复杂度为 \(O(n\log n)\),其中 n 是外层循环遍历每一个元素,而对于每个元素要执行复杂度为 \(\log n\) 的二分查找。空间复杂度为 \(O(n)\),需要额外数组空间存储数组的前 n 项和。

解法 3: 双指针

任意一个子序列都能有首位两个位置唯一确定,即使用首尾两个指针确定。双指针的方法巧妙之处在于快速的压缩搜索空间。

考虑一个子序列如果它的和没有达到大于等于 target 的要求,那么为了使其达到要求,要么在头部增加元素要么在尾部增加元素。如果在尾部逐步增加元素直到恰好满足要求,那么意味着以当前头指针开头的子序列的最优解已经找到,无需继续搜索。另外一方面,如果一个子序列的和大于 target,为了确定该子序列能否进一步缩短,要么在在头部减去元素,要么在尾部减去元素。如果在头部减去元素,直到恰好满足条件,那么说明以当前尾指针作为结尾的子序列的最优解已经找到,无需继续搜索。

如果以上两种情况有先后顺序,搜索空间会被进一步压缩。并且如果我们的指针从数组的一侧开始,指针的移动选择也被确定。例如头指针 head 和尾指针 tail 都等于零。那么此时如果不能满足和大于等于 target,则只能逐步增加尾指针。假如 tail = k 时是的首尾指针所确定的子序列恰好满足条件,那么此时 tail = k + 1 及以后的序列都不用考虑。至此与暴力解法的思路无二。接下来,在上一段中讨论到的,该序列已经满足大于等于 target 的条件,为了确定该序列能否缩短,我们只能尝试逐步增加头指针(因为一旦缩小尾指针必然导致不能满足条件)。此时,任何一步的移动都将把之前所有头指针的情况全部排除。例如 head=1 时仍然满足条件,那么说明 head=0 的任意满足条件的子序列都不会比 head=1 target=k 的子序列短了,所以 head=0 的所有序列被搜索完毕。同理继续增加头指针,直至不能满足条件。此时回到了第一种情况,同理只能选择增加尾指针,以此类推,将在 \(O(n)\) 复杂度内搜索完毕。

具体的代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var minSubArrayLen = function (target, nums) {
let s = 0, e = 0
let res = nums.length + 1
let sum = 0

while (e < nums.length) {
sum += nums[e]
while (sum - nums[s] >= target) {
sum -= nums[s]
s++
}
if (sum >= target) res = Math.min(res, e - s + 1)

e++
}
return res === nums.length + 1 ? 0 : res
};

代码中首尾指针均从零开始,在改变指针的时候相应的修改子序列的和 sum。外层 while 循环逐步增加尾指针,并在每次增加尾指针后判断是否满足条件(内层 while 循环的判断条件),当满足条件时尝试对现有序列进行压缩(内层 while 循环)。因为最后一次压缩后的序列肯定是当前外层循环内最短的序列,因此只需在内层循环外更新 res 的结果,但注意首先要使用 if 语句进行判断。

这里虽然采用了双层循环,但应该注意到首尾指针的值一直叠加,从未重置过。也就是说,首尾指针最多各移动 n 次。故时间复杂度为 \(O(n)\),空间复杂度为 \(O(1)\)

当然次算法也要求输入数组非负。

总结与思考

这道题双指针的使用非常巧妙,双指针作为一个常用的遍历技巧应当熟练掌握。前缀和(前 n 项和)也是一种技巧,可以将非负序列变为有序序列,进而便于查找。

还有一些细节需要注意:

  1. 对于下面代码

    1
    2
    3
    4
    while([exp]) { 
    // code block
    }
    // code line

    并不意味着 // code block 代码一定执行过。