Python O(n). Explanation and generalization to other subarray problems
Explanation for general contiguous subarray problems:\nProblems like this, that include a a) a contiguous subarray sum and b) find all/any instances of such sum
## Explanation for general contiguous subarray problems:\nProblems like this, that include a a) a contiguous subarray sum and b) find all/any instances of such sums that meet some condition, can be solved by the following template:\n\n1. Get the prefix sums array F=[0,a1,a1+a2,a1+...+an] or calculate as we go (preferable), holding the latest value in variable curr\n2. As we put together F, maintain a hash table with info on all F[j<i] (to be explained in a sec). If all possible values of F[i] are known, it may be faster to use a predefined array [1,0,...,0], otherwise use a dictionary.\n3. There will be a defining equation, i.e. a condition, that must be met for a contiguous subarray sum (a subarray is defined by its indices i,j. that\'s what we are solving for!). This will be of the form F[i]-F[j<i] = TARGET. The key construction is to re-arrange this into F[j<i] = F[i] - TARGET. Since all F[j<i] are already known, we can look up the quantity F[i] - TARGET in the hash table. This is O(1) time and so the total algo will be O(N)\n4. Do whatever we need with the knowledge in point 3. This is problem specific\n\nFor this problem we need that (sum(nums) - [subarray sum] )%p = 0. Pulling through the modulus operator we need [subarray sum]%p = sum(nums)%p. Defining K=sum(nums)%p this is F[j<i]%p = F[i]%p- K. This is almost the right form, if we take % every step of the way then it\'s easier to write F[j<i] = (F[i]-K)%p, with the understanding that all F\'s are modded by p. We now have the right form!\n\nPart 4 says do the problem specific thing. Three things. First see if F is in d (create dictionary, check). Second, store the index we last saw it at (let\'s us compute the size of a subarray). Third, see if size of a new subarray is less than that of any previous one we found. If it is, replace the global low with the current low.\n\n## Code\n```\n# intialize parameters\n# d[0] = 0 since the first element F[0] = 0 by definition\nK, tot, curr, d = sum(nums)%p, len(nums), 0, {0:0}\nif K == 0:\n\treturn 0\nfor i,x in enumerate(nums):\n\t# find latest element F[-1]\n\tcurr = (curr+x) % p\n\t# see if the target is in d\n\tif (curr-K) % p in d:\n\t\ttot = min(tot, i+1-d[(curr-K)%p])\n\t# F is of length 1 more than nums in general\n\t# since we loop 0,..,n-1, we need to add +1 to\n\t# simulate the range 1,...,n\n\td[curr] = i+1\n# the condition from part 4\nreturn (tot if tot < len(nums) else -1)\n```
[]