-
Notifications
You must be signed in to change notification settings - Fork 0
/
Minimum-Size-Subarray-Sum.go
119 lines (107 loc) · 3.18 KB
/
Minimum-Size-Subarray-Sum.go
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
package minimumsizesubarraysum
import (
"math"
"sort"
)
// MinSubArrayLenBurst : 暴力解 時間複雜 O(n^2), 空間複雜 O(1)
func MinSubArrayLenBurst(target int, nums []int) int {
lens := len(nums)
if lens <= 0 {
return 0
}
minSize := math.MaxInt32
for i := 0; i < lens; i++ {
sum := 0
for j := i; j < lens; j++ {
sum += nums[j]
if sum >= target {
minSize = min(minSize, j-i+1)
}
}
}
if minSize == math.MaxInt32 {
minSize = 0
}
return minSize
}
// MinSubArrayLenSlidingWindow : 滑動視窗 時間複雜 O(n), 空間複雜 O(1)
// 滑動窗口的精妙之處在於根據當前子序列和大小的情況,不斷調節子序列的起始位置。從而將O(n^2)的暴力解法降為O(n)
func MinSubArrayLenSlidingWindow(target int, nums []int) int {
lens := len(nums)
if lens <= 0 {
return 0
}
minSize := math.MaxInt32
start, end, sum := 0, 0, 0
for end < lens {
sum += nums[end]
for sum >= target {
minSize = min(minSize, end-start+1)
sum -= nums[start]
start++
}
end++
}
if minSize == math.MaxInt32 {
minSize = 0
}
return minSize
}
/*
MinSubArrayLenBinarysearch : 前缀和 + 二分查找 O(nlog(n))
為了使用二分查找,需要額外創建一個數組 sums 用於存儲數組nums 的前綴和,其中 sums[i] 表示從 nums[0] 到 nums[i−1] 的元素和。
得到前綴和之後,對於每個開始下標i,可通過二分查找得到大於或等於 i 的最小下標 bound,
使得 sums[bound]-sums[i-1] >= s,
並更新子數組的最小長度(此時子數組的長度是 bound -(i-1) )。
C++ 的 lower_bound,Java 的 Arrays.binarySearch
因為這道題保證了數組中每個元素都為正,所以前綴和一定是遞增的,這一點保證了二分的正確性。如果題目沒有說明數組中每個元素都為正,這裡就不能使用二分來查找這個位置了。
*/
func MinSubArrayLenBinarysearch(target int, nums []int) int {
lens := len(nums)
if lens <= 0 {
return 0
}
minSize := math.MaxInt32
// sums[i] 表示從 nums[0] 到 nums[i−1]
sums := make([]int, lens+1)
// 為了方便計算 size = lens + 1
// sums[0] = 0, 前0個的元素和
// sums[1] = nums[0] , 前1個元素和為 nums[0]
for i := 1; i <= lens; i++ {
sums[i] = sums[i-1] + nums[i-1]
}
// fmt.Println("sums", sums)
for i := 1; i <= lens; i++ {
/*
target 7
input 2 3 1 2 4 3
-----------------------------------
i 0 1 2 3 4 5 6
-----------------------------------
sums 0 2 5 6 8 12 15 // input 的前 n 個元素和
tmpTarge 7 9 12 13 15 19 // tmpTarge = target + sums[i-1]
bound 4 5 5 6 6 7 // bound = sort.SearchInts(sums, tmpTarge)
bound-(i-1) 4 4 3 3 2 2
minSize 4 4 3 3 2 2
*/
tmpTarge := target + sums[i-1]
bound := sort.SearchInts(sums, tmpTarge)
// if bound < 0 {
// bound = -bound - 1
// }
if bound <= lens {
minSize = min(minSize, bound-(i-1))
}
// fmt.Println("i:", i, " tmpTarge", tmpTarge, " bound:", bound, " bound-(i-1)", bound-(i-1), " minSize:", minSize)
}
if minSize == math.MaxInt32 {
minSize = 0
}
return minSize
}
func min(x, y int) int {
if x < y {
return x
}
return y
}