-
Notifications
You must be signed in to change notification settings - Fork 0
/
lintcode404.cpp
39 lines (35 loc) · 1.15 KB
/
lintcode404.cpp
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
// 這題剛開始我用prefix sum作
// 然後列舉每個區間來查詢,結果發現會TLE
// 後來用三指針解:左指針固定,右二指針找尋bound
int subarraySumII(vector<int> &A, int start, int end) {
int n = A.size();
int count = 0;
// R為右開區間
int left = 0, minR = 0, maxR = 0;
int minSum = 0, maxSum = 0;
while(left < n) {
// 有可能會有left > right的情況
// 也就是right遲遲未行動
// 這種情況下我們要讓right至少行動到left的位置
minR = max(minR, left);
maxR = max(maxR, left);
while(minR < n && minSum + A[minR] < start) {
minSum += A[minR];
minR++;
}
while(maxR < n && maxSum + A[maxR] <= end) {
maxSum += A[maxR];
maxR++;
}
count += maxR - minR;
// 注意若為left和R同體的情況
// 那就代表根本沒加上A[left]
// 那我們更不能減掉
if(minR > left)
minSum -= A[left];
if(maxR > left)
maxSum -= A[left];
left++;
}
return count;
}