子数组问题

发布日期: 2023-06-12

更新日期: 2023-06-17

文章字数: 768

阅读时长: 3 分

阅读次数:

问题

常见的一些关于字数组问题，比如子数组之和等于某个值，小于某个值，大于某个值，然后获取满足这种条件的子数组的个数，长度，一般这类问题的通常解法有滑动窗口（双指针），前缀和 + 哈希。
滑动窗口是定义两个指针变量，初始化的时候，指针变量同时在起点位置，然后开始移动右指针，每次移动一个位置，当触发某个条件，比如大于某个值，等于某个和，这个时候开始移动左指针，来收缩边界，其中这里需要注意的是，当数组求和的时候，如果是数组元素存在负数，这个时候，扩大窗口范围，求和反而变小，这种情况就不适合用滑动窗口，需要该用其他算法来实现。
前缀和 + 哈希是定义以一个新的数组，这个数组长度是原数组长度加1，一开始就从数组1开始开始到结尾，记录到该位置的前n项和。然后转化为两数之差的问题上，并用hash记录

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
```
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
```

1 <= target <= 109
1 <= nums.length <= 105

1 <= nums[i] <= 105
分析：这道题总结下来就是求最小长度的子数组之和是大于等于目标值，其中数据集给出数组元素都大于0，这种就是典型的用双指针的方式来实现
代码：

func minSubArrayLen(target int, nums []int) int {
  length := len(nums)
  i, j := 0, 0
  minLen := 100001
  sum := 0
  for j < length {
      sum += nums[j]
      for sum >= target {
          if j - i + 1 < minLen {
              minLen = j - i + 1
          }
          sum -= nums[i]
          i++
      }
      j++

  }
  if minLen == 100001{
      return 0
  }
  return minLen
}

时间复杂度为O（2n），即O（n），空间复杂度为O（1）

给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数
```
输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况
```

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000

-107 <= k <= 107
分析：由于数组元素中包含负数，所以不能用滑动窗口的解法，
代码：

func subarraySum(nums []int, k int) int {
 n := len(nums)
  ans := 0
  numMap := make(map[int]int)
  numMap[0] = 1
  preSum := 0
  for start := 0; start < n; start++ {
      preSum += nums[start]
      v, ok := numMap[preSum - k]
      if ok {
          ans += v
      }
      v1, ok :=  numMap[preSum]
      if ok {
          numMap[preSum] = v1 + 1
      }else {
          numMap[preSum] = 1
      }
  }
  return ans
}