Minimun Size Subarray Sum
不想解释…
my solution
简单思考了一下, 以每个元素为起点, 循环往右找到满足条件的数
最终做比较, 就可以得出答案
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
| func minSubArrayLen(s int, nums []int) int {
size := len(nums)
ret := size
var sum int = 0
for _, v := range(nums) {
sum += v
}
if (sum < s) {
return 0
}
for i, v := range(nums) {
sum = v
counter := 1
for i2 := i + 1; i2 < size && sum < s; i2++ {
sum += nums[i2]
counter++
}
if sum >= s && counter < ret {
ret = counter
}
}
return ret
}
|
这样的复杂度大概是 O(n2), 同时为了区别特殊情况, 还做了一次…
the best solution
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
| func minSubArrayLen(s int, nums []int) int {
size := len(nums)
ret := size + 1
start := 0
var sum int = 0
for i, v := range(nums) {
sum += v
for sum >= s && sum - nums[start] >= s {
sum -= nums[start]
start++
}
if sum >= s && i - start + 1 < ret {
ret = i - start + 1
}
}
if ret == size + 1 {
return 0
}
return ret
}
|
其实这是我将算法思想重写后的代码…
简单来说, 就是先找到匹配的 sum, 然后没加一次, 就尝试减少前面的数
这样遍历之后, 得到的数同样也是最短的
(我很好奇没有是否没有人对数级的解决方案…)