作者：蘚小凤_950 | 来源：互联网 | 2023-09-14 14:53
Tips：FB爱考原题，但是基本需要给到最优解，如果先给出一般解法再给出优化思路，时间往往来不及。分享面试遇到的题。给定一个由n个正整数组成的数组和一个正整数
Tips：FB 爱考原题，但是基本需要给到最优解，如果先给出一般解法再给出优化思路，时间往往来不及。
分享面试遇到的题。
给定一个由 n 个正整数组成的数组和一个正整数 s，请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解，则返回 -1 。
做题地址
样例 1:
1
2
3
| 输入: [2,3,1,2,4,3], s = 7
输出: 2
解释: 子数组 [4,3] 是该条件下的最小长度子数组。 |
样例 2:
1
2
| 输入: [1, 2, 3, 4, 5], s = 100
输出: -1 |
解题思路
- 如果采用暴力解法，用变量 i 从左到右遍历数组，变量 j 从 i 到数组尾部遍历，将 i 到 j 内的元素遍历求和，找到和大于 s 的最短数组。时间复杂度为 O(n^3)。
- 对暴力法进行优化，使用累加器来进行求和，那么求和这步只需要 O(1)。总的时间复杂度为 O(n^2)。
- 使用二分法来继续优化，对于左端点 i，我们用二分法来寻找 j 。首先建立前缀和数组 sum，对于每个 i，在 i 到尾部这段区间上二分查找，找到满足 sum[j] - sum[i] > S 的最小的 j 。总的时间复杂度为 O(nlog(n))。
- 最优解法是采用滑窗。我们用 2 个指针，一个指向子数组开始的位置，一个指向数子组最后的位置，并维护区间内的和 curr_sum 大于等于 s 同时数组长度最小，实时更新最短的数组长度 res 。时间复杂度为 O(n)。
算法流程
- 初始化左指针 left 和右指针 right 指向 0，子数组和 curr_sum 为 0 。
- 右指针 right 遍历 nums 数组，即不断移动滑窗右端
- 更新子数组的和，curr_sum += nums[right]
- 当子数组和满足条件，即 curr_cum >= s 时
- 更新 res = min(res, right - left + 1)，其中 right - left + 1 是当前子数组的长度
- curr_sum -= nums[left]，然后左指针右移，继续判断当前数组和是否满足条件
- 返回 res
复杂度分析
- 时间复杂度：O(n) 。每个指针移动都需要 O(n)的时间。每个元素至多被访问两次，一次被右端点访问，一次被左端点访问。
- 空间复杂度：O(1)。变量只需要常数空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class Solution {
/**
* @param nums: an array of integers
* @param s: An integer
* @return: an integer representing the minimum size of subarray
*/
public int minimumSize(int[] nums, int s) {
int left = 0, currSum = 0, res = Integer.MAX_VALUE;
for (int right = 0; right
// 滑窗右边界扩张
currSum += nums[right];
// 满足条件
while (currSum >= s) {
// 更新 res
res = Math.min(res, right - left + 1);
// 滑窗左边界收缩
currSum -= nums[left];
left ++;
}
}
return res == Integer.MAX_VALUE ? -1: res;
}
} |
厉害！大佬是在面试当场想出 O(n)时间的解法的？
LeetCode
209. Minimum Size Subarray Sum
京公网安备 11010802041100号