Best window, no repeats
The largest sum of k in a row, all different. About 12 minutes.
What does the window need to know?
Some windows need to track two things at once. Here you need each window's total, and you need to know whether every number in it is different.
Ask yourself: what's the smallest amount of information that lets me judge a window? Then, as the window slides, update each piece for the number coming in and the number going out, and only then test the window.
- sum
- 10
- best
- 10
- distinct
- 3
Window 1, 5, 4: all different (the count map has 3 keys). Sum 10.
To know whether all the numbers in a sliding window are different, what's enough to keep track of?
- AA count for each value in the window
- BJust the total
- CThe largest value
Show the answer
A count for each value in the window. All k numbers are different exactly when k values each appear once.
Best window, no repeats
You get a list of numbers and k. Among the runs of exactly k consecutive numbers in which all k numbers are different, return the largest sum. If there is no such run, return 0.
nums = [1, 5, 4, 2, 9, 9, 9], k = 3 → 15
1 ≤ k ≤ n ≤ 1,000,000 · 1 ≤ each value ≤ 10^6 · return a long