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
Appearance settings

Commit 845a0df

Browse filesBrowse files
BlankjBlankj
committed
add 0209
1 parent dbe51e8 commit 845a0df
Copy full SHA for 845a0df

File tree

5 files changed

+172
-75
lines changed
Filter options

5 files changed

+172
-75
lines changed

‎README.md

Copy file name to clipboardExpand all lines: README.md
+5-2Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -85,7 +85,8 @@
8585
| 49 | [Group Anagrams][0049] | Hash Table, String |
8686
| 50 | [Pow(x, n)][0050] | Math, Binary Search |
8787
| 56 | [Merge Intervals][0056] | Array, Sort |
88-
| 209 | [长度最小的子数组(Minimum Size Subarray Sum)][0209] | Array, Sort |
88+
| 209 | [长度最小的子数组(Minimum Size Subarray Sum)][0209] | 数组、双指针、二分查找 |
89+
| 215 | [数组中的第K个最大元素(Kth Largest Element in an Array)][0215] | 堆、分治算法 |
8990
| 554 | [Brick Wall][0554] | Hash Table |
9091
| 1014 | [最佳观光组合(Best Sightseeing Pair)][1014] | 数组 |
9192

@@ -168,11 +169,13 @@
168169
[0049]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0049/README.md
169170
[0050]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0050/README.md
170171
[0056]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0056/README.md
172+
[0209]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0209/README.md
173+
[0215]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0215/README.md
171174
[0554]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0554/README.md
172175
[1014]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/1014/README.md
176+
173177
[0004]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0004/README.md
174178
[0010]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0010/README.md
175-
176179
[0023]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0023/README.md
177180
[0025]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0025/README.md
178181
[0030]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/0030/README.md

‎note/0209/README.md

Copy file name to clipboardExpand all lines: note/0209/README.md
+71-45Lines changed: 71 additions & 45 deletions
Original file line numberDiff line numberDiff line change
@@ -2,80 +2,106 @@
22

33
## 题目描述
44

5-
我们从二叉树的根节点 `root` 开始进行深度优先搜索。
5+
给定一个含有 **n** 个正整数的数组和一个正整数 **s** ，找出该数组中满足其和 **≥ s** 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。
66

7-
在遍历中的每个节点处，我们输出 `D` 条短划线（其中 `D` 是该节点的深度），然后输出该节点的值。（_如果节点的深度为 `D`，则其直接子节点的深度为 `D + 1`。根节点的深度为 `0`）。_
8-
9-
如果节点只有一个子节点，那么保证该子节点为左子节点。
10-
11-
给出遍历输出 `S`，还原树并返回其根节点 `root`。
12-
13-
**示例 1：**
14-
15-
**![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/04/12/recover-a-tree-from-preorder-traversal.png)**
7+
**示例：**
168

179
```
18-
输入："1-2--3--4-5--6--7"
19-
输出：[1,2,5,3,4,6,7]
10+
输入：s = 7, nums = [2,3,1,2,4,3]
11+
输出：2
12+
解释：子数组 [4,3] 是该条件下的长度最小的连续子数组。
2013
```
2114

22-
**示例 2：**
15+
**进阶：**
2316

24-
**![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/04/12/screen-shot-2019-04-10-at-114101-pm.png)**
17+
* 如果你已经完成了 _O_(_n_) 时间复杂度的解法, 请尝试 _O_(_n_ log _n_) 时间复杂度的解法。
2518

26-
```
27-
输入："1-2--3---4-5--6---7"
28-
输出：[1,2,5,3,null,6,null,4,null,7]
29-
```
19+
**标签：** 数组、双指针、二分查找
3020

31-
**示例 3：**
3221

33-
![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/04/12/screen-shot-2019-04-10-at-114955-pm.png)
22+
## 思路 0
3423

35-
```
36-
输入："1-401--349---90--88"
37-
输出：[1,401,null,349,88,90]
24+
直接暴力法，两重 for 循环，记录最小长度即可，代码很简单，如下所示：
25+
26+
27+
```java
28+
class Solution {
29+
public int minSubArrayLen(int s, int[] nums) {
30+
int ans = Integer.MAX_VALUE;
31+
for (int i = 0; i < nums.length; i++) {
32+
int sum = nums[i];
33+
if (sum >= s) {
34+
return 1;
35+
}
36+
for (int j = i + 1; j < nums.length; j++) {
37+
sum += nums[j];
38+
if (sum >= s) {
39+
ans = Math.min(ans, j - i + 1);
40+
break;
41+
}
42+
}
43+
}
44+
return ans == Integer.MAX_VALUE ? 0 : ans;
45+
}
46+
}
3847
```
3948

40-
**提示：**
49+
## 思路 1
4150

42-
* 原始树中的节点数介于 `1` 和 `1000` 之间。
43-
* 每个节点的值介于 `1` 和 `10 ^ 9` 之间。
51+
对上面进行优化，我们通过首位两个指针来模拟滑动窗口，如果加起来值小于 s，则向右扩大窗口直至不小于 s，然后固定窗口右侧来向左缩小窗口，同时更新符合条件的最小窗口长度即可，代码如下所示：
4452

45-
**标签：** 树、深度优先搜索
53+
```java
54+
class Solution {
55+
public int minSubArrayLen(int s, int[] nums) {
56+
int left = 0, right = 0, sum = 0, ans = Integer.MAX_VALUE;
57+
while (right < nums.length) {
58+
sum += nums[right++]; // 向右扩大窗口
59+
while (sum >= s) { // 如果不小于 s，则收缩窗口左边界
60+
ans = Math.min(ans, right - left);// 更新结果
61+
sum -= nums[left++]; // 向左缩小窗口
62+
}
63+
}
64+
return ans == Integer.MAX_VALUE ? 0 : ans;
65+
}
66+
}
67+
```
4668

69+
## 思路 2
4770

48-
## 思路
71+
进阶中说了，尝试使用 O(nlogn) 时间复杂度的解法，由于数组都是正整数构成，所以前缀和一定是递增的，想到的应该就是用二分查找了，可以用 sums 数组来存储 nums 数组的前缀和，sums[i] 代表 nums[0] 到 nums[i - 1] 总和，然后遍历 sums 数组，对 sums[i] + s 进行二分查找然后不断更新结果即可，具体代码如下所示：
4972

50-
直接暴力两层 for 循环肯定过不了关，我们把公式变化为 `(A[i] + i) + (A[j] - j)`，看到此应该就可以想到在每次遍历 `j` 时，只需要知道 `max(A[i] + i)` 即可。
5173

5274
```java
5375
class Solution {
54-
55-
public int maxScoreSightseeingPair(int[] A) {
56-
int ans = 0, cur = A[0] + 0;
57-
for (int j = 1; j < A.length; j++) {
58-
ans = Math.max(ans, cur + A[j] - j); // 计算当前最大得分
59-
cur = Math.max(cur, A[j] + j); // 更新最大的 A[i] + i
76+
public int minSubArrayLen(int s, int[] nums) {
77+
int ans = Integer.MAX_VALUE;
78+
int[] sums = new int[nums.length + 1];
79+
for (int i = 0; i < nums.length; i++) {
80+
sums[i + 1] = sums[i] + nums[i];
6081
}
61-
return ans;
62-
}
63-
64-
public static void main(String[] args) {
65-
Solution solution = new Solution();
66-
int[] A = new int[]{8, 1, 5, 2, 6};
67-
System.out.println(solution.maxScoreSightseeingPair(A));
82+
for (int i = 0; i < nums.length; i++) {
83+
int target = s + sums[i]; // 确定要搜索的目标值
84+
// Java 二分查找 Arrays.binarySearch 如果找到就会返回该元素的索引；
85+
// 如果没找到就会返回一个负数，这个负数取反之后再减一就是查找的值应该在数组中的位置；
86+
// 例如 [-1, 0, 1, 5] 中二分查找 2，其返回值就是 -4，其 -(-4) - 1 = 3，所以 2 这个元素插入到数组的索引就是 3
87+
int bound = Arrays.binarySearch(sums, target);
88+
if (bound < 0) {
89+
bound = -bound - 1;
90+
}
91+
if (bound < sums.length) { // 当 bound 确定插入点不在 sums 数组的最后面时，说明不小于 target 的值了
92+
ans = Math.min(ans, bound - i);
93+
}
94+
}
95+
return ans == Integer.MAX_VALUE ? 0 : ans;
6896
}
6997
}
70-
7198
```
7299

73-
74100
## 结语
75101

76102
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-java-leetcode][ajl]
77103

78104

79105

80-
[title]: https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal
106+
[title]: https://leetcode-cn.com/problems/minimum-size-subarray-sum
81107
[ajl]: https://github.com/Blankj/awesome-java-leetcode

‎note/1014/README.md

Copy file name to clipboardExpand all lines: note/1014/README.md
-1Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,6 @@ class Solution {
4646
System.out.println(solution.maxScoreSightseeingPair(A));
4747
}
4848
}
49-
5049
```
5150

5251

‎src/com/blankj/hard/_1028/Solution.java

Copy file name to clipboardExpand all lines: src/com/blankj/hard/_1028/Solution.java
+26-27Lines changed: 26 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,32 @@
1313
* </pre>
1414
*/
1515
public class Solution {
16+
// public TreeNode recoverFromPreorder(String S) {
17+
// char[] chars = S.toCharArray();
18+
// int len = chars.length;
19+
// List<TreeNode> levels = new LinkedList<>();
20+
// for (int i = 0; i < len; ) {
21+
// int level = 0, val = 0;
22+
// while (chars[i] == '-') { // 获取所在层级，Character.isDigit() 会比较慢
23+
// ++i;
24+
// ++level;
25+
// }
26+
// while (i < len && chars[i] != '-') { // 获取节点的值
27+
// val = val * 10 + chars[i++] - '0';
28+
// }
29+
// TreeNode curNode = new TreeNode(val);
30+
// if (level > 0) {
31+
// TreeNode parent = levels.get(level - 1);
32+
// if (parent.left == null) { // 如果节点只有一个子节点，那么保证该子节点为左子节点。
33+
// parent.left = curNode;
34+
// } else {
35+
// parent.right = curNode;
36+
// }
37+
// }
38+
// levels.add(level, curNode); // 因为是前序遍历（根-左-右），也就是右覆盖左时，此时左树已遍历完成，故无需考虑覆盖问题
39+
// }
40+
// return levels.get(0);
41+
// }
1642

1743
public TreeNode recoverFromPreorder(String S) {
1844
char[] chars = S.toCharArray();
@@ -44,33 +70,6 @@ public TreeNode recoverFromPreorder(String S) {
4470
return stack.get(0);
4571
}
4672

47-
// public TreeNode recoverFromPreorder(String S) {
48-
// char[] chars = S.toCharArray();
49-
// int len = chars.length;
50-
// List<TreeNode> levels = new LinkedList<>();
51-
// for (int i = 0; i < len; ) {
52-
// int level = 0, val = 0;
53-
// while (chars[i] == '-') { // 获取所在层级，Character.isDigit() 会比较慢
54-
// ++i;
55-
// ++level;
56-
// }
57-
// while (i < len && chars[i] != '-') { // 获取节点的值
58-
// val = val * 10 + chars[i++] - '0';
59-
// }
60-
// TreeNode curNode = new TreeNode(val);
61-
// if (level > 0) {
62-
// TreeNode parent = levels.get(level - 1);
63-
// if (parent.left == null) { // 如果节点只有一个子节点，那么保证该子节点为左子节点。
64-
// parent.left = curNode;
65-
// } else {
66-
// parent.right = curNode;
67-
// }
68-
// }
69-
// levels.add(level, curNode); // 因为是前序遍历（根-左-右），也就是右覆盖左时，此时左树已遍历完成，故无需考虑覆盖问题
70-
// }
71-
// return levels.get(0);
72-
// }
73-
7473
public static void main(String[] args) {
7574
Solution solution = new Solution();
7675
TreeNode.print(solution.recoverFromPreorder("1-2--3--4-5--6--7"));

‎src/com/blankj/medium/_0209/Solution.java

Copy file name to clipboard
+70Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
package com.blankj.medium._0209;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* <pre>
7+
* author: Blankj
8+
* blog : http://blankj.com
9+
* time : 2020/06/30
10+
* desc :
11+
* </pre>
12+
*/
13+
public class Solution {
14+
// public int minSubArrayLen(int s, int[] nums) {
15+
// int ans = Integer.MAX_VALUE;
16+
// for (int i = 0; i < nums.length; i++) {
17+
// int sum = nums[i];
18+
// if (sum >= s) {
19+
// return 1;
20+
// }
21+
// for (int j = i + 1; j < nums.length; j++) {
22+
// sum += nums[j];
23+
// if (sum >= s) {
24+
// ans = Math.min(ans, j - i + 1);
25+
// break;
26+
// }
27+
// }
28+
// }
29+
// return ans == Integer.MAX_VALUE ? 0 : ans;
30+
// }
31+
32+
// public int minSubArrayLen(int s, int[] nums) {
33+
// int left = 0, right = 0, sum = 0, ans = Integer.MAX_VALUE;
34+
// while (right < nums.length) {
35+
// sum += nums[right++]; // 向右扩大窗口
36+
// while (sum >= s) { // 如果不小于 s，则收缩窗口左边界
37+
// ans = Math.min(ans, right - left);// 更新结果
38+
// sum -= nums[left++]; // 向左缩小窗口
39+
// }
40+
// }
41+
// return ans == Integer.MAX_VALUE ? 0 : ans;
42+
// }
43+
44+
public int minSubArrayLen(int s, int[] nums) {
45+
int ans = Integer.MAX_VALUE;
46+
int[] sums = new int[nums.length + 1];
47+
for (int i = 0; i < nums.length; i++) {
48+
sums[i + 1] = sums[i] + nums[i];
49+
}
50+
for (int i = 0; i < nums.length; i++) {
51+
int target = s + sums[i]; // 确定要搜索的目标值
52+
// Java 二分查找 Arrays.binarySearch 如果找到就会返回该元素的索引；
53+
// 如果没找到就会返回一个负数，这个负数取反之后再减一就是查找的值应该在数组中的位置；
54+
// 例如 [-1, 0, 1, 5] 中二分查找 2，其返回值就是 -4，其 -(-4) - 1 = 3，所以 2 这个元素插入到数组的索引就是 3
55+
int bound = Arrays.binarySearch(sums, target);
56+
if (bound < 0) {
57+
bound = -bound - 1;
58+
}
59+
if (bound < sums.length) { // 当 bound 确定插入点不在 sums 数组的最后面时，说明不小于 target 的值了
60+
ans = Math.min(ans, bound - i);
61+
}
62+
}
63+
return ans == Integer.MAX_VALUE ? 0 : ans;
64+
}
65+
66+
public static void main(String[] args) {
67+
Solution solution = new Solution();
68+
System.out.println(solution.minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3}));
69+
}
70+
}

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.