1590.Make the array and energyPDivide

topic：

1590.Make the array and energyPDivide.md

Thought：

‘≡’Together
For example nums=[11,2,5,7,8,9]，p=10，So [5,7] Remove，The remaining numbers add 30，Be able to p Divide。
All elements and $42mod10 = 2$
设All elements andx，RemoveElementsand为y，Makex-y Be able topDivide,satisfy

y≡x(mod p)->x % p = y % p

By prefix and，The problem converts：Find two numbers on the prefix and array s[left] and s[right]，satisfy right−left Minimum

$$
s[right] - s[left] ≡ x (mod p)
->s[right] - x ≡ s[left] (mod p)
$$

((s[right]-x)modp+p) mod p = s[left] mod p

Traversal sss At the same time，Hash table last\textit{last}last Record s[i]mod p The last time the bidding appeared，if lastlast Contain
(s[i] mod p−x mod p+p) mod p，Let’s set its corresponding setting j，So [j,i) Is a符合topic要求的子数组。

Enumerate i，Calculate the minimum value of the child array length that meets the requirements，Is the answer。if没有符合要求的子数组，Then return −1。

Code implementation，You can initialize the answer to nums length n。if最后答案等于 n，It means that there are no sub -array that does not meet the requirements，因为topic不允许将整个数组都移除。

lastIs amap，The key is an integer，Value is an integer。j, ok := last[(v-x+p)%p]This line code is inlastThe search key is(v-x+p)%pElements，And give its value to variablesj。if这个键不存在，SookThe value will befalse，otherwiseokThe value will betrue。
The return value of this grammar is two values，The first value is the value corresponding to the key，第二个值Is a布尔值，Indicates whether the key exists。
ifokThe value istrue，SoCode中的ifThe statement will be executed，It willansThe value update isi-jandansMinimum value。ifokThe value isfalse，SoifThe statement will be skipped，The program will continue to execute。

Code：

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        s = list(accumulate(nums, initial=0))
        x = s[-1] % p
        if x == 0: return 0  # Remove the air array（This line can not be）

        ans = n = len(nums)
        last = {}
        for i, v in enumerate(s):
            last[v % p] = i
            j = last.get((v - x) % p, -n)  # if不存在，-n Be guaranteed i-j >= n
            ans = min(ans, i - j)
        return ans if ans < n else -1

package main

func minSubarray(nums []int, p int) int {
	n := len(nums)
	s := make([]int, n+1)
	for i, v := range nums {
		s[i+1] = (s[i] + v) % p
	}
	x := s[n]
	if x == 0 {
		return 0
	}

	ans := n
	last := map[int]int{}
	for i, v := range s {
		last[v] = i
		if j, ok := last[(v-x+p)%p]; ok {
			ans = min(ans, i-j)
		}
	}
	if ans < n {
		return ans
	}
	return -1
}

func min(a, b int) int {
	if b < a {
		return b
	}
	return a
}