FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
JavaArithmetic/src/LeetCode/LeetCode209.java at master · git-jhy/JavaArithmetic · GitHub
git-jhy
JavaArithmetic
Repository navigation
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
JavaArithmetic
/
src
/
LeetCode
/
LeetCode209.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
175 lines (138 loc) · 5.08 KB
Breadcrumbs
JavaArithmetic
/
src
/
LeetCode
/
LeetCode209.java
Copy path
File metadata and controls
175 lines (138 loc) · 5.08 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
package
LeetCode
;
public
class
LeetCode209
{
// https://leetcode.com/problems/minimum-size-subarray-sum/description/
// 暴力解法
// 该方法在 Leetcode 中会超时！
// 时间复杂度: O(n^3)
// 空间复杂度: O(1)
public
int
minSubArrayLen
(
int
s
,
int
[]
nums
) {
if
(
s
<=
0
||
nums
==
null
)
throw
new
IllegalArgumentException
(
"Illigal Arguments"
);
int
res
=
nums
.
length
+
1
;
for
(
int
l
=
0
;
l
<
nums
.
length
;
l
++)
for
(
int
r
=
l
;
r
<
nums
.
length
;
r
++) {
int
sum
=
0
;
for
(
int
i
=
l
;
i
<=
r
;
i
++)
sum
+=
nums
[
i
];
if
(
sum
>=
s
)
res
=
Math
.
min
(
res
,
r
-
l
+
1
);
}
// 无解的情况
if
(
res
==
nums
.
length
+
1
)
return
0
;
return
res
;
}
// 优化暴力解
// 时间复杂度: O(n^2)
// 空间复杂度: O(n)
public
int
minSubArrayLen2
(
int
s
,
int
[]
nums
) {
if
(
s
<=
0
||
nums
==
null
)
throw
new
IllegalArgumentException
(
"Illigal Arguments"
);
// sums[i]存放nums[0...i-1]的和
int
[]
sums
=
new
int
[
nums
.
length
+
1
];
sums
[
0
] =
0
;
for
(
int
i
=
1
;
i
<=
nums
.
length
;
i
++)
sums
[
i
] =
sums
[
i
-
1
] +
nums
[
i
-
1
];
int
res
=
nums
.
length
+
1
;
for
(
int
l
=
0
;
l
<
nums
.
length
;
l
++)
for
(
int
r
=
l
;
r
<
nums
.
length
;
r
++){
// 使用sums[r+1] - sums[l] 快速获得nums[l...r]的和
if
(
sums
[
r
+
1
] -
sums
[
l
] >=
s
)
res
=
Math
.
min
(
res
,
r
-
l
+
1
);
}
// 无解的情况
if
(
res
==
nums
.
length
+
1
)
return
0
;
return
res
;
}
// 滑动窗口的思路
// 时间复杂度: O(n)
// 空间复杂度: O(1)
public
int
minSubArrayLen3
(
int
s
,
int
[]
nums
) {
if
(
s
<=
0
||
nums
==
null
)
throw
new
IllegalArgumentException
(
"Illigal Arguments"
);
int
l
=
0
,
r
= -
1
;
// nums[l...r]为我们的滑动窗口
int
sum
=
0
;
int
res
=
nums
.
length
+
1
;
while
(
l
<
nums
.
length
){
// 窗口的左边界在数组范围内,则循环继续
if
(
r
+
1
<
nums
.
length
&&
sum
<
s
)
sum
+=
nums
[++
r
];
else
// r已经到头 或者 sum >= s
sum
-=
nums
[
l
++];
if
(
sum
>=
s
)
res
=
Math
.
min
(
res
,
r
-
l
+
1
);
}
// 无解的情况
if
(
res
==
nums
.
length
+
1
)
return
0
;
return
res
;
}
// 另外一个滑动窗口的实现, 仅供参考
// 时间复杂度: O(n)
// 空间复杂度: O(1)
public
int
minSubArrayLen4
(
int
s
,
int
[]
nums
) {
if
(
s
<=
0
||
nums
==
null
)
throw
new
IllegalArgumentException
(
"Illigal Arguments"
);
int
l
=
0
,
r
= -
1
;
// [l...r]为我们的窗口
int
sum
=
0
;
int
res
=
nums
.
length
+
1
;
while
(
r
+
1
<
nums
.
length
){
// 窗口的右边界无法继续扩展了, 则循环继续
while
(
r
+
1
<
nums
.
length
&&
sum
<
s
)
sum
+=
nums
[++
r
];
if
(
sum
>=
s
)
res
=
Math
.
min
(
res
,
r
-
l
+
1
);
while
(
l
<
nums
.
length
&&
sum
>=
s
){
sum
-=
nums
[
l
++];
if
(
sum
>=
s
)
res
=
Math
.
min
(
res
,
r
-
l
+
1
);
}
}
if
(
res
==
nums
.
length
+
1
)
return
0
;
return
res
;
}
// 时间复杂度: O(nlogn)
// 空间复杂度: O(n)
// 二分搜索
public
int
minSubArrayLen5
(
int
s
,
int
[]
nums
) {
if
(
s
<=
0
||
nums
==
null
)
throw
new
IllegalArgumentException
(
"Illigal Arguments"
);
// sums[i]存放nums[0...i-1]的和
int
[]
sums
=
new
int
[
nums
.
length
+
1
];
sums
[
0
] =
0
;
for
(
int
i
=
1
;
i
<=
nums
.
length
;
i
++)
sums
[
i
] =
sums
[
i
-
1
] +
nums
[
i
-
1
];
int
res
=
nums
.
length
+
1
;
for
(
int
l
=
0
;
l
<
nums
.
length
-
1
;
l
++){
// Java类库中没有内置的lowerBound方法，
// 我们需要自己实现一个基于二分搜索的lowerBound:)
int
r
=
lowerBound
(
sums
,
sums
[
l
] +
s
);
if
(
r
!=
sums
.
length
){
res
=
Math
.
min
(
res
,
r
-
l
);
}
}
if
(
res
==
nums
.
length
+
1
)
return
0
;
return
res
;
}
// 在有序数组nums中寻找大于等于target的最小值
// 如果没有（nums数组中所有值都小于target），则返回nums.length
private
int
lowerBound
(
int
[]
nums
,
int
target
){
if
(
nums
==
null
/*|| !isSorted(nums)*/
)
throw
new
IllegalArgumentException
(
"Illegal argument nums in lowerBound."
);
int
l
=
0
,
r
=
nums
.
length
;
// 在nums[l...r)的范围里寻找解
while
(
l
!=
r
){
int
mid
=
l
+ (
r
-
l
) /
2
;
if
(
nums
[
mid
] >=
target
)
r
=
mid
;
else
l
=
mid
+
1
;
}
return
l
;
}
public
static
void
main
(
String
[]
args
) {
int
[]
nums
= {
2
,
3
,
1
,
2
,
4
,
3
};
int
s
=
7
;
System
.
out
.
println
((
new
LeetCode209
()).
minSubArrayLen
(
s
,
nums
));
}
}
Back
|
FazBrowse Home
|
New Git URL