Shortest Subarray Whose Distinct-Value Sum Reaches a Target

Given an array of positive integers `nums` and a positive integer `target`, return the length of the shortest contiguous subarray whose distinct sum is at least `target`. The distinct sum of a subarray adds each different value once, however many times that value occurs in the subarray: the distinct sum of `[3, 3, 2]` is `3 + 2 = 5`. Return `0` if no subarray qualifies. ### Function Signature ```python def shortest_distinct_sum_subarray(nums: list[int], target: int) -> int: ``` ### Rules - A subarray is a nonempty run of consecutive elements `nums[i], nums[i + 1], ..., nums[j]`. Its length is `j - i + 1` and counts every element, including repeated ones. - A value that occurs several times in the subarray, next to each other or apart, adds to the distinct sum once. - Return the smallest length among all subarrays whose distinct sum is at least `target`, or `0` if there is none. ### Constraints - `1 <= len(nums) <= 10^5` - `1 <= nums[i] <= 10^4` - `1 <= target <= 10^9` - every distinct sum is below `10^8`, so all values fit in a 32-bit signed integer ### Examples **Example 1** ```text Input: nums = [5, 5, 1, 2, 6], target = 9 Output: 3 ``` `[1, 2, 6]` has distinct sum 9. No subarray of length 2 qualifies: as an ordinary sum `[5, 5]` would give 10, but its distinct sum is 5, and the best pair, `[2, 6]`, reaches only 8. **Example 2** ```text Input: nums = [4, 4, 4, 3], target = 8 Output: 0 ``` An ordinary sum would accept `[4, 4]`, but no subarray has a distinct sum above `4 + 3 = 7`. **Example 3** ```text Input: nums = [4, 2, 2, 5], target = 11 Output: 4 ``` A distinct sum of 11 needs all three values 4, 2 and 5, and only the whole array contains both the 4 and the 5. Its length, 4, counts the repeated 2.