Show problems as
Classic problem #560MediumArrayHash TablePrefix Sum

Subarray Sum Equals K

Real-world version: Trail Elevation Stretches
Tracked in this browser only
Read Subarray Sum Equals K on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstPrefix Sums · Dynamic Programming, animated step by step

A survey crew has split a hiking trail into numbered segments laid end to end. deltas[i] is the signed elevation change in metres across segment i: positive on a climb, negative on a descent, zero across flat ground.

A stretch is one or more segments hiked back to back, with no gaps. The net elevation change of a stretch is the sum of the changes of its segments.

Given deltas and an integer target, return how many stretches have a net elevation change of exactly target. Two stretches count separately whenever they begin or end on different segments, even if their nets match and even if one sits inside the other.

A stretch always covers at least one segment; there is no empty stretch.

Examples

Example 1

Input
deltas = [40, -40, 40], target = 40
Output
3

Segment 0 alone, segment 2 alone, and all three segments together each net 40 metres. The descent in the middle cancels the first climb, which is why the full trail also qualifies.

Example 2

Input
deltas = [12, 5, -5, 7], target = 12
Output
2

Segment 0 on its own nets 12, and segments 0 through 2 net 12 as well because the 5 metre rise is undone by the 5 metre drop.

Example 3

Input
deltas = [-3, -3, -3], target = -6
Output
2

Segments 0 and 1 form one qualifying stretch and segments 1 and 2 form another. They overlap, so both are counted.

Constraints

  • 1 <= deltas.length <= 2 * 10^4
  • -1000 <= deltas[i] <= 1000
  • -10^7 <= target <= 10^7

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_elevation_stretches(deltas: list[int], target: int) -> int:
Java
public int countElevationStretches(int[] deltas, int target)

More on the same topics