Golang: O(n) with prefix sums and hash table (w/ intuition & comments)
Why Sliding Window Doesn\'t Work\n\nBecause when adding a number to the right end of the sliding window, the remainder of the subarray sum can either go down or
# Why Sliding Window Doesn\'t Work\n\nBecause when adding a number to the right end of the sliding window, the remainder of the subarray sum can either go down or up, which implies that we won\'t know when to remove the number at the left end of the sliding window. This is similar to [560. Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/description/) where the input can contain negative numbers.\n\n# Intuition\n\n- Let `r = sum(nums) % p`, we want to find the shortest subarray `A` s.t. `sum(A) % p == r`\n- There are `n^2` subarrays in total, so brute force takes `O(n^2)`.\n- If we want to do it in `O(n)`, then we need to find a way to check all the prefix/suffix sums of `nums[:i]` in `O(1)`, which usually implies using a hash table.\n- Assume that the prefix sums are stored in `m` the map, then its content can be visualized as below (let\'s temporarily ignore the modulo part for simplicity, and we just want to know if any of the subarray sum is equal to `r`):\n  `nums[0]`\n  `nums[0]` + `nums[1]`\n  `...`\n  `nums[0]` + `nums[1]` + `...` + `nums[i-1]` + `nums[i]`\n- If we directly check if `r` is in `m`, then we\'re just checking some subarrays that start at `0`, while we need those subarrays to either start or end at `i`.\n- Can we somehow check all the subarrays that end at `i`?\n- Observation, or another perspective to view `m` (i.e., the existing bottom left triangle and the "imaginary" upper right triangle in **bold**):\n  **`nums[0]`** + **`nums[1]`** + **`nums[2]`** + **`...`** + **`nums[i-1]`** + **`nums[i]`**\n  `nums[0]` + **`nums[1]`** + **`nums[2]`** + **`...`** + **`nums[i-1]`** + **`nums[i]`**\n  `nums[0]` + `nums[1]` + **`nums[2]`** + **`...`** + **`nums[i-1]`** + **`nums[i]`**\n  `...`\n  `nums[0]` + `nums[1]` + `nums[2]` + `...` + **`nums[i-1]`** + **`nums[i]`**\n  `nums[0]` + `nums[1]` + `nums[2]` + `...` + `nums[i-1]` + **`nums[i]`**\n- Observe that the bold entries are essentially all the subarrays that end at `i`. In other words, to check if the sum of any of them is `r`, we can **check if `sum(nums[:i+1]) - r` is in `m`**. There are 2 gotchas though:\n  - We need to do the check before inserting `sum(nums[:i+1])` into `m` (i.e., `nums[i]` above is in bold, which means that it\'s not yet in `m`).\n  - The first row above are all in bold, which means that before the loop begins, `m` should be initialized with a single entry whose key is `0`, and its value shall be either `-1` if it\'s defined to be the index of the start of the prefix or `0` if it\'s defined to be the length of the prefix.\n- Last, to account for the modulo part, the remainder of the sums instead of the sums themselves will be stored in `m`.\n\n# Code\n\n```golang []\n// TC: O(n)\n// SC: O(n)\nfunc minSubarray(nums []int, p int) int {\n    r := 0\n    for _, n := range nums {\n        r = (r + n) % p\n    }\n    if r == 0 {\n        return 0\n    }\n\n    ans := len(nums)\n    sums := map[int]int{0: -1}\n    sum := 0\n    for i := range nums {\n        sum = (sum + nums[i]) % p\n        if j, ok := sums[(sum + p - r) % p]; ok && i - j < ans { // + p to ensure the result to be nonnegative\n            ans = i - j\n        }\n        // The following line could override an existing entry in sums,\n        // which implies there\'s a longer prefix with the same remainder,\n        // which in turn implies that we may be able to find a shorter suffix with the same remainder,\n        // which is what we want, so no special handling is needed here.\n        sums[sum] = i\n    }\n    if ans == len(nums) {\n        return -1\n    }\n    return ans\n}\n```
['Go']