Trim Both Ends to a Total
All items of nums are positive. You repeatedly remove either the first or the last remaining item, and you stop as soon as the removed items add up to exactly goal. Return the fewest removals that can reach goal, or -1 if no sequence of removals does.
The removed items always form a prefix plus a suffix of nums, so what remains is a contiguous middle stretch whose sum is the total of nums minus goal; the longest such stretch gives the fewest removals. Removing every item is allowed, and the middle stretch may then be empty.
Example 1
Remove the last item 3 and then the new last item 2: 3 + 2 = 5 in two removals.
Example 2
The smallest item is 5, so no removal can total exactly 4.
Constraints
1 <= len(nums) <= 1001 <= nums[i] <= 1001 <= goal <= 10000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.