前缀和习题

// 使用滑动窗口思路
func minSubArrayLen(target int, nums []int) int {
   l := 0
   n := len(nums)
   ans := n + 1
   pre := 0
   for r, v := range nums {
      pre += v
      for pre >= target {
         if r-l+1 < ans {
            ans = r - l + 1
         }
         pre -= nums[l]
         l++
      }
   }
   if ans == n+1 {
      return 0
   }
   return ans
}

package preSum

func maxSubArrayLen(nums []int, k int) int {
   ans := 0
   d := map[int]int{0: -1}
   pre := 0
   for r, v := range nums {
      pre += v
      if idx, err := d[pre-k]; err {
         if r-idx > ans {
            ans = r - idx
         }
      }
      if _, err := d[pre]; !err {
         d[pre] = r
      }
   }
   return ans
}

package preSum

// 连续的子数组和
func checkSubarraySum(nums []int, k int) bool {
   // 此处是有一个定理的
   // 同余定理
   // (x+y)%6
   d := map[int]int{0: -1}
   pre := 0
   for r, v := range nums {
      pre = (pre + v) % k
      if idx, err := d[pre]; err {
         if r-idx >= 2 {
            return true
         }
      } else {
         d[pre] = r
      }
   }
   return false
}

package preSum

func findMaxLength(nums []int) int {
   ans := 0
   d := map[int]int{0: -1}
   pre := 0
   for k, v := range nums {
      if v == 1 {
         pre++
      } else {
         pre--
      }
      if idx, err := d[pre]; err {
         if k-idx > ans {
            ans = k - idx
         }
      } else {
         d[pre] = k
      }
   }
   return ans
}

package preSum

func subarraySum(nums []int, k int) int {
   ans := 0
   d := map[int]int{0: 1}
   pre := 0
   for _, v := range nums {
      pre += v
      if cnt, err := d[pre-k]; err {
         ans += cnt
      }
      d[pre]++

   }
   return ans
}

package preSum

import "sort"

func arrayPairSum(nums []int) int {
   sort.Ints(nums)
   ans := 0
   for i := 0; i < len(nums); i += 2 {
      ans += nums[i]
   }
   return ans
}

package preSum

func numSubarrayProductLessThanK(nums []int, k int) int {
   ans := 0
   l := 0
   pre := 1
   for r, v := range nums {
      pre *= v
      for l <= r && pre >= k {
         pre /= nums[l]
         l++
      }
      if pre < k {
         ans += r - l + 1
      }
   }
   return ans
}

package preSum

// 和可被 K 整除的子数组
// 优秀参考
// https://leetcode.cn/problems/make-sum-divisible-by-p/solutions/809758/shu-zu-zheng-chu-wen-ti-hui-zong-qian-zh-xzjc/
func subarraysDivByK(nums []int, k int) int {
   // (x+y)%k==0
   d := map[int]int{0: 1}
   ans := 0
   pre := 0
   for _, v := range nums {
      pre += v
      // go语言取模 会出现负数 -->处理为 (pre%k+k)%k
      d[(pre%k+k)%k] += 1
   }
   for _, v := range d {
      ans += v * (v - 1) / 2
   }
   return ans
}

package preSum

func canMakePaliQueries(s string, queries [][]int) []bool {
   nums := []int{0}
   for k, v := range s {
      nums = append(nums, nums[k]^(1<<(int(v)-97)))
   }
   ans := []bool{}
   for _, v := range queries {
      l, r, k := v[0], v[1], v[2]
      ans = append(ans, func(num int) (res int) {
         for num > 0 {
            res += num & 1
            num >>= 1
         }
         return
      }(nums[l]^nums[r+1])/2 <= k)
   }
   return ans
}

package preSum

// 1590. 使数组和能被 P 整除
func minSubarray(nums []int, p int) int {
   // (s-sub)%p==0-->s%p==sub%p
   s := 0
   for _, v := range nums {
      s += v
   }
   tmp := s % p
   if tmp == 0 {
      return 0
   }

   d := map[int]int{0: -1}
   pre := 0
   n := len(nums)
   ans := n
   for r, v := range nums {
      pre += v
      cur, pre := pre%p, (pre-tmp+p)%p
      if idx, err := d[pre]; err {
         dis := r - idx
         if ans > dis {
            ans = dis
         }
      }
      d[cur] = r
   }
   if ans == n {
      return -1
   }
   return ans
}