A fundraiser records how much it raised each day in nums; every day raises a positive amount. Write shortest_run(nums: list[int], target: int) -> int that returns the length of the shortest run of consecutive days whose total is at least target, or 0 if even all the days together fall short.
shortest_run([3, 1, 2, 5, 1, 4], 8) # 3 ([1, 2, 5]; no two neighbours reach 8)
shortest_run([2, 9, 1, 1], 9) # 1 ([9])
shortest_run([4, 2, 6], 12) # 3 (it takes every day)
shortest_run([1, 1, 1], 5) # 0
1 <= len(nums) <= 2 * 10^5; each value is in[1, 10^5];1 <= target <= 10^11. Totals can exceed 32 bits (use 64-bit integers in C++/Java).- Trying every start with every end is O(n²), too slow for the large tests. Aim for O(n).
Show hint
because every value is positive, extending a run only raises its total and trimming its start only lowers it. For each end day, the best start never moves left as the end moves right.