Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 7020b8a

Browse files
Merge pull request SharingSource#535 from SharingSource/ac_oier
✨feat: add 209
2 parents 4217b25 + f4a1c9d commit 7020b8a

File tree

4 files changed

+87
-1
lines changed

4 files changed

+87
-1
lines changed

‎Index/二分.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,7 @@
1010
| [153. 寻找旋转排序数组中的最小值](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/solution/gong-shui-san-xie-yan-ge-olognyi-qi-kan-6d969/) | 中等 | 🤩🤩🤩 |
1111
| [154. 寻找旋转排序数组中的最小值 II](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/solution/gong-shui-san-xie-xiang-jie-wei-he-yuan-7xbty/) | 困难 | 🤩🤩🤩 |
1212
| [162. 寻找峰值](https://leetcode-cn.com/problems/find-peak-element/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/find-peak-element/solution/gong-shui-san-xie-noxiang-xin-ke-xue-xi-qva7v/) | 中等 | 🤩🤩🤩🤩🤩 |
13+
| [209. 长度最小的子数组](https://leetcode.cn/problems/minimum-size-subarray-sum/) | [LeetCode 题解链接](https://leetcode.cn/problems/minimum-size-subarray-sum/solution/by-ac_oier-c5jm/) | 中等 | 🤩🤩🤩🤩🤩 |
1314
| [220. 存在重复元素 III](https://leetcode-cn.com/problems/contains-duplicate-iii/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/contains-duplicate-iii/solution/gong-shui-san-xie-yi-ti-shuang-jie-hua-d-dlnv/) | 中等 | 🤩🤩🤩 |
1415
| [240. 搜索二维矩阵 II](https://leetcode-cn.com/problems/search-a-2d-matrix-ii/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/gong-shui-san-xie-yi-ti-shuang-jie-er-fe-y1ns/) | 中等 | 🤩🤩🤩🤩 |
1516
| [274. H 指数](https://leetcode-cn.com/problems/h-index/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/h-index/solution/gong-shui-san-xie-li-yong-er-duan-xing-z-1jxw/) | 中等 | 🤩🤩🤩 |

‎Index/前缀和.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
| 题目 | 题解 | 难度 | 推荐指数 |
22
| ------------------------------------------------------------ | ------------------------------------------------------------ | ---- | -------- |
33
| [187. 重复的DNA序列](https://leetcode-cn.com/problems/repeated-dna-sequences/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/repeated-dna-sequences/solution/gong-shui-san-xie-yi-ti-shuang-jie-hua-d-30pg/) | 中等 | 🤩🤩🤩🤩 |
4+
| [209. 长度最小的子数组](https://leetcode.cn/problems/minimum-size-subarray-sum/) | [LeetCode 题解链接](https://leetcode.cn/problems/minimum-size-subarray-sum/solution/by-ac_oier-c5jm/) | 中等 | 🤩🤩🤩🤩🤩 |
45
| [304. 二维区域和检索 - 矩阵不可变](https://leetcode-cn.com/problems/range-sum-query-2d-immutable/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/range-sum-query-2d-immutable/solution/xia-ci-ru-he-zai-30-miao-nei-zuo-chu-lai-ptlo/) | 中等 | 🤩🤩🤩🤩🤩 |
56
| [303. 区域和检索 - 数组不可变](https://leetcode-cn.com/problems/range-sum-query-immutable/) | [LeetCode 题解链接](https://leetcode-cn.com/problems/range-sum-query-immutable/solution/sha-shi-qian-zhui-he-ya-tu-jie-qian-zhui-0rla/) | 简单 | 🤩🤩🤩🤩🤩 |
67
| [327. 区间和的个数](https://leetcode.cn/problems/count-of-range-sum/) | [LeetCode 题解链接](https://leetcode.cn/problems/count-of-range-sum/solution/by-ac_oier-b36o/) | 困难 | 🤩🤩🤩 |
Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
### 题目描述
2+
3+
这是 LeetCode 上的 **[209. 长度最小的子数组](https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/gong-shui-san-xie-yi-ti-shuang-jie-er-we-esm9/)** ,难度为 **中等**。
4+
5+
Tag : 「前缀和」、「二分」
6+
7+
8+
9+
给定一个含有 `n` 个正整数的数组和一个正整数 `target`。
10+
11+
找出该数组中满足其和 `≥ target` 的长度最小的 连续子数组 $[nums_l, nums_{l+1}, ..., nums_{r-1}, nums_r]$ ,并返回其长度。如果不存在符合条件的子数组,返回 0ドル$ 。
12+
13+
示例 1:
14+
```
15+
输入:target = 7, nums = [2,3,1,2,4,3]
16+
17+
输出:2
18+
19+
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
20+
```
21+
示例 2:
22+
```
23+
输入:target = 4, nums = [1,4,4]
24+
25+
输出:1
26+
```
27+
示例 3:
28+
```
29+
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
30+
31+
输出:0
32+
```
33+
34+
提示:
35+
* 1ドル <= target <= 10^9$
36+
* 1ドル <= nums.length <= 10^5$
37+
* 1ドル <= nums[i] <= 10^5$
38+
39+
---
40+
41+
### 前缀和 + 二分
42+
43+
利用 $nums[i]$ 的数据范围为 $[1, 10^5],ドル可知前缀和数组满足「单调递增」。
44+
45+
我们先预处理出前缀和数组 `sum`(前缀和数组下标默认从 1ドル$ 开始),对于每个 $nums[i]$ 而言,假设其对应的前缀和值为 $s = sum[i + 1],ドル我们将 $nums[i]$ 视为子数组的右端点,问题转换为:在前缀和数组下标 $[0, i]$ 范围内找到满足 **值小于等于 $s - t$** 的最大下标,充当子数组左端点的前一个值。
46+
47+
利用前缀和数组的「单调递增」(即具有二段性),该操作可使用「二分」来做。
48+
49+
代码:
50+
```Java
51+
class Solution {
52+
public int minSubArrayLen(int t, int[] nums) {
53+
int n = nums.length, ans = n + 10;
54+
int[] sum = new int[n + 10];
55+
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
56+
for (int i = 1; i <= n; i++) {
57+
int s = sum[i], d = s - t;
58+
int l = 0, r = i;
59+
while (l < r) {
60+
int mid = l + r + 1 >> 1;
61+
if (sum[mid] <= d) l = mid;
62+
else r = mid - 1;
63+
}
64+
if (sum[r] <= d) ans = Math.min(ans, i - r);
65+
}
66+
return ans == n + 10 ? 0 : ans;
67+
}
68+
}
69+
```
70+
* 时间复杂度:预处理前缀和数组的复杂度为 $O(n),ドル遍历前缀和数组统计答案复杂度为 $O(n\log{n})$。整体复杂度为 $O(n\log{n})$
71+
* 空间复杂度:$O(n)$
72+
73+
---
74+
75+
### 最后
76+
77+
这是我们「刷穿 LeetCode」系列文章的第 `No.209` 篇,系列开始于 2021年01月01日,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
78+
79+
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
80+
81+
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
82+
83+
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
84+

‎LeetCode/551-560/560. 和为 K 的子数组(中等).md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -22,7 +22,7 @@ Tag : 「前缀和」、「哈希表」
2222
```
2323

2424
提示:
25-
* 1ドル <= nums.length <= 2 * 10^4$
25+
* 1ドル <= nums.length <= 2 \times 10^4$
2626
* $-1000 <= nums[i] <= 1000$
2727
* $-10^7 <= k <= 10^7$
2828

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /