Along one side of a road there is a sequence of vacant plots of land. Each plot has a different area (non-zero). So, the areas form a sequence A[1], A[2], … A[N].
You want to buy K acres of land to build a house. You want to find a segment of continguous plots (i.e., a subsection in the sequence) of minimum length whose sum is exactly K.
Solution
First attempt
Compute prefix sums. For each (i,j) check if A[j] - A[i] = K. Among all such sections, choose the one where j - i is minimized.
This takes time N2. Can we do better?
The prefix sums form a sequence of values in ascending value:
P[1] < P[2] < … < P[N]
For each i, we want to find a j such that P[j] - P[i] = K. Since the prefix sums are sorted in ascending order, we can find the j for each i using binary search, instead of exhaustively scanning P[i+1], … P[N].
This improves the complexity to N log N.
Can we do it in time proportional to N?
For each i, compute if there is a segment starting at i that adds up to exactly K.
Start at A[1]. Add A[2], A[3], …
Essentially we maintain a sliding window within which we maintain the sum. At each stage:
Example
K = 8 1 3 2 1 4 1 3 2 1 1 2
Expand window right till sum crosses K
1 3 2 1 4 1 3 2 1 1 2 |--->4--->6--->7-->11
Exceeds K, contract window from left
1 3 2 1 4 1 3 2 1 1 2 |------------>10
Exceeds K, contract window from left
1 3 2 1 4 1 3 2 1 1 2 |------->7
Less than K, expand window to right
1 3 2 1 4 1 3 2 1 1 2 |------------->8
Equals K, note left and right end points, contract from left
1 3 2 1 4 1 3 2 1 1 2 |-------->6
Less than K, expand window to right
1 3 2 1 4 1 3 2 1 1 2 |------------->9
Exceeds K, contract window from left
1 3 2 1 4 1 3 2 1 1 2 |-------->8
Equals K, note left and right end points, contract from left
1 3 2 1 4 1 3 2 1 1 2 |--->4
Less than K, expand window to right
1 3 2 1 4 1 3 2 1 1 2 |--->4--->6--->7--->8
Equals K, note left and right end points, contract from left
1 3 2 1 4 1 3 2 1 1 2 |------------->7
Less than K, expand window to right
1 3 2 1 4 1 3 2 1 1 2 |------------->7--->9
Exceeds K, contract window from left
1 3 2 1 4 1 3 2 1 1 2 |------------->7
Less than K, cannot expand window to right, stop
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky