基础知识：常见双指针算法分为三类，同向（即两个指针都相同一个方向移动），背向（两个指针从相同或者相邻的位置出发，背向移动直到其中一根指针到达边界为止），相向（两个指针从两边出发一起向中间移动直到两个指针相遇）

练习题

基础知：常见双指针算法分为三类，同向（即两个指针都相同一个方向移动），背向（两个指针从相同或者相邻的位置出发，背向移动直到其中一根指针到达边界为止），相向（两个指针从两边出发一起向中间移动直到两个指针相遇）

背向双指针(基本都是回文串问题)

1.1.1. 最长回文串 (opens new window)

给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。

在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。

class Solution:
  def longestPalindrome(self, s: str) -> int:

      ans = 0
      count = collections.Counter(s)

      for v in count.values():

          ans += v//2 * 2

          if v%2 ==1 and ans %2 ==0:
              ans += 1
      return ans
      

// Make sure to add code blocks to your code group

1.1.2. 验证回文串 (opens new window)

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

class Solution:
  def isPalindrome(self, s: str) -> bool:
      ss = re.findall(r'[a-zA-Z0-9]', s)
      
      left, right = 0, len(ss) - 1
      while left < right:
          if ss[left].lower() == ss[right].lower():
              left += 1
              right -= 1
          else:
              return False
      return True
      

// Make sure to add code blocks to your code group

1.1.3. 最长回文子串 (opens new window)

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

class Solution:
  def longestPalindrome(self, s: str) -> str:
      """
      动态规划
      dp[i][j] 以s[i]开头以s[j]结尾的字符为回文子串

      dp[i][j] = True ---> s[i] = s[j] （dp[i+1][j-1] = True or
                  j-i<3）
      初始化dp数组
      """
      if len(s)<2:
          return s 
      dp = [[False] * len(s) for _ in range(len(s))]
      max_len = 1
      start = 0
      for i in range(len(s)):
          dp[i][i] = True
      for j in range(1,len(s)):
          for i in range(j):
              if s[i] != s[j]:
                  continue
              if dp[i+1][j-1] or j-i+1<=3:
                  dp[i][j] = True
              
              if dp[i][j] and j-i+1>max_len:
                  max_len = j-i+1
                  start = i
      return s[start:start+max_len]

func longestPalindrome(s string) string {
  /*
  dp[i][j]: 字串s[i][j]是回文字串

  dp[i][j] =True --->s[i]=s[j] && dp[i+1][j-1] =True or j-i+1<3
  */
  if len(s)<2{
      return s 
  }
  dp := make([][]bool, len(s))
  for i:=0;i<len(s);i++{
      dp[i] = make([]bool, len(s))
      dp[i][i] = true 
  }
  max_len := 1
  start := 0
  for j:=0;j<len(s);j++{
      for i:=0;i<j;i++{
          if s[i] != s[j]{
              continue
          }
          if dp[i+1][j-1] || j-i+1<=3{
              dp[i][j] = true
          }
          if dp[i][j]==true&&j-i+1>max_len{
              max_len = j-i+1
              start = i 
          }
      }
  }
  return s[start:start+max_len]
  }

// Make sure to add code blocks to your code group

1.1.4. 回文子串 (opens new window)

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

笔记

// 奇数回文串的“中心”是一个具体的字符，例如：回文串 "aba" 的中心是字符 "b"；
// 偶数回文串的“中心”是位于中间的两个字符的“空隙”，例如：回文串串 "abba" 的中心是两个 "b" 中间的那个“空隙”。

class Solution:
  def countSubstrings(self, s: str) -> int:

      def extend(s: str, i: int, j:int, n:int):
          res = 0
          while (i>=0 and j<n and s[i]== s[j]):
              i -= 1
              j += 1
              res += 1
          return res
      res = 0
      for i in range(len(s)):
          # 回文串的中心可能是一个字符，也有可能是两个字符
          res += extend(s, i, i, len(s))
          res += extend(s, i, i+1, len(s))
      return res

func countSubstrings(s string) int {

  n := len(s)
  res := 0
  for i := range n{
      // 寻找以s[i]为中心点的回文串
      res += extend(s, i, i, n)
      // 寻找以[s[i], s[i+1]]为中心点的回文串
      res += extend(s, i, i+1, n)
  }
  return res
}

func extend(s string, i int, j int, n int) int{

  res := 0
  for (i>=0 && j<n && s[i] == s[j]){
      i -= 1
      j += 1
      res += 1
  }
  return res
}

// Make sure to add code blocks to your code group

相向双指针(基本是sum问题)

笔记

以two sum为基础的一系列题

1.2.1.两数之和 (opens new window)

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

:::

可以使用hashmap 解法，这里使用相向双指针的解法

:::

class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
      li = [(index, val) for index, val in enumerate(nums)] # 索引和元素左映射
      li = sorted(li, key=lambad x:x[1], reverser = False)   # 按照元素排序

      left = 0
      right = len(nums)-1
      while left < right:
          if li[left][1] + li[right][1] == target:
              return [li[left][0], li[right][0]]
          elif li[left][1] + li[right][1] > target:
              right -= 1
          else:
              left += 1
      return []

func twoSum(nums []int, target int) []int {
  li := make([][2]int, 0)
  for index, val := range nums{
      li = append(li, [2]int{index, val})
  }
  sort.SliceStable(li, func(i, j int) bool {
  return li[i][1] < li[j][1]
  })

  // sort.Ints(nums)
  n := len(li)
  left, right := 0, n-1
  for left<right{
      if li[left][1] + li[right][1] == target{
          return []int{li[left][0], li[right][0]}
      } else if li[left][1] + li[right][1] > target{
          right --
      } else{
          left ++
      }
  }
  return []int{-1, -1}

}

// Make sure to add code blocks to your code group

1.2.2.两数之和 II - 输入有序数组 (opens new window)

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

class Solution:
  def twoSum(self, numbers: List[int], target: int) -> List[int]:
      """
      二分法可以优化时间
      双指针法也可以
      """

      left, right = 0, len(numbers)-1

      while left < right:
          if numbers[left] + numbers[right] == target:
              return [left+1, right+1]
          elif numbers[left] + numbers[right] < target:
              left += 1
          else:
              right -= 1
          

func twoSum(numbers []int, target int) []int {
  n := len(numbers)
  left, right := 0, n - 1
  for left < right{
      if numbers[left] + numbers[right] == target{
          return []int{left+1, right+1}
      } else if numbers[left] + numbers[right] > target{
          right--
      } else{
          left++
      }
  }
  return []int{-1, -1}

}

// Make sure to add code blocks to your code group

1.2.3.三数之和 (opens new window)

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

笔记

先排序，利用排序后的有序性进行去重和指针移动

class Solution:
  def threeSum(self, nums: List[int]) -> List[List[int]]:
      """
      排序， 防止重复
      前后双指针法
      """
      nums.sort()
      ret = []
      for i in range(len(nums)):
          if i>0 and nums[i] == nums[i-1]:
              continue
          first = nums[i]
          target = -first
          left, right = i +1, len(nums) -1
          while left < right:
              if nums[left] + nums[right] == target:
                  ret.append([first, nums[left], nums[right]])
                  while left <right and nums[left+1] == nums[left]:
                      left += 1
                  
                  while left < right and nums[right-1] == nums[right]:
                      right -= 1
              elif nums[left] + nums[right] > target:
                  right -= 1
                  continue
              else:
                  left += 1
                  continue
              left += 1
              right -= 1
      return ret

func threeSum(nums []int) [][]int {
  sort.Ints(nums)
  n := len(nums)
  ret := make([][]int, 0)
  for i:= 0;i<n;i++{
      if i>0 && nums[i] == nums[i-1]{
          continue
      }
      first := nums[i]
      target := -first
      left := i+1
      right := n -1
      for left<right{
          if nums[left]+nums[right] == target{
              ret = append(ret, []int{first, nums[left], nums[right]})
              for left <right && nums[left] == nums[left+1]{
                  left++
              } 
              for left <right && nums[right] == nums[right-1]{
                  right--
              }
          } else if nums[left] + nums[right] > target{
              right--
              continue
          } else{
              left++
              continue
          }
          left++
          right--

      }
      
  }
  return ret

}

// Make sure to add code blocks to your code group

1.2.4.最接近的三数之和 (opens new window)

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2：

输入：nums = [0,0,0], target = 1
输出：0

class Solution:
  def threeSumClosest(self, nums: List[int], target: int) -> int:
      nums.sort()
      l = len(nums)
      num = 10000
      for i in range(l):
          if i> 0 and nums[i] == nums[i-1]:
              continue
          first = nums[i]
          m,n = i+1, l-1
          while m<n:
              second = nums[m]
              third = nums[n]
              temp = first + second + third
              if  temp== target:
                  return target
              if abs(target - temp) < abs(target-num):
                  num = temp
              if temp > target:
                  n -= 1
              else:
                  m += 1
      return num
              

func threeSumClosest(nums []int, target int) int {
  minNum := int(math.Pow(10, 5))
  n := len(nums)
  sort.Ints(nums)
  for i:= 0;i<n;i++{
      if i>0 && nums[i] == nums[i-1]{
          continue
      }
      left := i+1
      right := n-1
      for left <right{
          cur := nums[i] + nums[left] + nums[right]
          if cur == target{
              return cur
          }
          if math.Abs(float64(target-cur)) < math.Abs(float64(target-minNum)){
              minNum = cur
          }
          if cur <target{
              left++
          } else{
              right--
          }
      }
  }
  return minNum
}

// Make sure to add code blocks to your code group

1.2.5.四数之和 (opens new window)

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

class Solution:
  def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
      n = len(nums)
      nums.sort()
      ret = list()
      for first in range(n):
          if first>0 and nums[first] == nums[first-1]:
              continue
          for second in range(first+1, n-2):
              if second>first+1 and nums[second] == nums[second-1]:
                  continue
              third = second+1
              forth = n -1
              while third<forth:
                  cur = nums[first]+nums[second]+nums[third]+nums[forth]
                  if cur == target:
                      ret.append([nums[first], nums[second],nums[third], nums[forth]])
                      while third<forth and nums[third] == nums[third+1]:
                          third+=1
                      while third<forth and nums[forth] == nums[forth-1]:
                          forth-=1
                  elif cur >target:
                      forth-=1
                      continue
                  else:
                      third+=1
                      continue
                  forth-=1
                  third+=1
      return ret

func fourSum(nums []int, target int) [][]int {
  sort.Ints(nums)
  ret := make([][]int, 0)
  n:= len(nums)
  for first:=0;first<n-3;first++{
      if first>0 && nums[first-1] == nums[first]{
          continue
      }
      for second:= first+1;second<n-2;second++{
          if second>first+1 && nums[second-1] == nums[second]{
              continue
          }

          left :=  second +1
          right := n -1
          for left<right{
              temp := nums[first] + nums[second] + nums[left] + nums[right]
              if temp == target{
                  ret = append(ret, []int{nums[first], nums[second], nums[left], nums[right]})
                  for left <right && nums[left] == nums[left+1]{
                      left++
                  }
                  for left<right&& nums[right] == nums[right-1]{
                      right--
                  }
              } else if temp > target{
                  right--
                  continue
                  
              }else{
                  left++
                  continue
              }
              left++
              right--
          }
      }
  }
  return ret
}

// Make sure to add code blocks to your code group

1.2.6.四数相加 II (opens new window)

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

笔记

分为A B和C D两组，组内元素相互组合求和, 得到AB和CD的列表，列表长度为N*N；

AB和CD排序；

定义指针p = 0, pe = N*N, p从小到大遍历AB列表， pe从大到小遍历CD列表， 如果p和pe对应元素的和大于0， pe左移；如果小于0，p右移。如果和恰好为0，这个时候统计 AB列表中和p对应元素的值 相等的个数、 CD列表中和pe对应元素的值 相等的个数，个数的乘积加到最后的结果中。

class Solution:
  def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
      N = len(A)
      c = 0
      AB = []
      CD = []
      for i in range(0,N):
          for j in range(0,N):
              AB.append(A[i]+B[j])
      for k in range(0,N):
          for l in range(0,N):
              CD.append(C[k]+D[l])
      AB = sorted(AB)
      CD = sorted(CD)
      p = 0
      pe = N*N - 1 
      while pe>=0 and p<N*N:
          if AB[p]+CD[pe]==0:
              oldp = p
              oldpe = pe
              p = p + 1
              while p<N*N and AB[p] == AB[oldp]:
                  p = p + 1
              pe = pe - 1
              while pe>=0 and CD[pe] == CD[oldpe]:
                  pe = pe - 1
              c = c + (p-oldp)*(oldpe-pe)
              continue
          if AB[p]+CD[pe]>0:
              pe = pe - 1
              continue
          if AB[p]+CD[pe]<0:
              p = p + 1
              continue
      return c

// Make sure to add code blocks to your code group

###1.2.7盛最多水的容器 (opens new window)

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

class Solution:
  def maxArea(self, height: List[int]) -> int:
      """
      双指针法
      盛水最多的容器
      v = (l-r+1) * min(l, r)
      最多需要记录最大值
      """
      max_v = 0
      l, r = 0, len(height)-1

      while l<r:
          v = (r-l)*(min(height[l], height[r]))
          if max_v < v:
              max_v = v 

          if height[l]<height[r]:
              l += 1
          else:
              r -= 1
      return max_v

func maxArea(height []int) int {
  // v = (right - left +1) * min(height[left], height[right])
  max_v := 0
  left := 0
  right := len(height)-1
  for left < right{
      v := max(right-left)*min(height[left], height[right])
      if max_v < v{
          max_v = v 
      }
      if height[left]<height[right]{
          left += 1
      }else{
          right -= 1
      }
  }
  return max_v
}

// Make sure to add code blocks to your code group

同向双指针

1.3.1.移动零 (opens new window)

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

笔记

使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。

右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。

注意到以下性质：

左指针左边均为非零数；

右指针左边直到左指针处均为零。

因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。

解释一下：如果数组没有0，那么快慢指针始终指向同一个位置，每个位置自己和自己交换；如果数组有0，快指针先走一步，此时慢指针对应的就是0，所以要交换。

class Solution:
  def moveZeroes(self, nums: List[int]) -> None:
      """
      Do not return anything, modify nums in-place instead.
      """
      p = 0
      for q in range(len(nums)):
          if nums[q] != 0:
              nums[p], nums[q] = nums[q], nums[p]
              p += 1
      

func moveZeroes(nums []int)  {

  n := len(nums)
  p := 0
  for q := range n{
      if nums[q] != 0{
          nums[p], nums[q] = nums[q], nums[p]
          p++
      }
  }
}

// Make sure to add code blocks to your code group

1.3.2. 删除有序数组中的重复项 (opens new window)

给你一个 非严格递增排列 的数组 nums ，请你** 原地 (opens new window)** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

• 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
• 返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

class Solution:
  def removeDuplicates(self, nums: List[int]) -> int:
      """
      两个指针，一个指针指向不重复元素的末尾，一个指针遍历
      """
      left = 0
      for right in range(1, len(nums)):
          if nums[right] == nums[left]:
              continue
          else:
              left +=1
              nums[left] = nums[right]
      return left+1

func removeDuplicates(nums []int) int {

  newPtr := 0
  for curPtr := 1; curPtr<len(nums);curPtr++{
      if nums[newPtr] != nums[curPtr]{
          newPtr += 1
          nums[newPtr], nums[curPtr] = nums[curPtr], nums[newPtr]

      }
  }
  return newPtr + 1

}

// Make sure to add code blocks to your code group

1.3.3.替换后的最长重复字符 (opens new window)

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。

在执行上述操作后，返回 包含相同字母的最长子字符串的长度。

示例 1：

输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例 2：

输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
可能存在其他的方法来得到同样的结果。

笔记

这是一道经典的双指针问题。问题的重点在于K的长度。 我们创建l、r指针和一个空字典d，r指针一路往右，每次指向的字符判断是否在字典中。 如果不存在加入字典并赋值为1，存在则value值+1。 当r -l + 1即所有字符 - max(d.values()) > k，则表示允许替换的字符超过了k此时需要不断右移l，并在同时将l指向的字符从d中删除。 一路比较下来，最终的结果，就是我们最常子串长度。

class Solution:
  def characterReplacement(self, s: str, k: int) -> int:

      if len(s) <=1:
          return len(s)
      n = len(s)
      left = 0
      right = 0
      count = collections.defaultdict(int)
      ret = 0
      # 在[left, right]中最多替换k个字符可以得到只有一种的字符串
      while right< n:
          count[s[right]] += 1
          while (right-left + 1) - max(count.values()) >k:
              count[s[left]] -= 1
              left += 1
          ret = max(ret, right-left + 1)
          right += 1

      return ret

func characterReplacement(s string, k int) int {
  left, right, n := 0, 0, len(s)
  mp := map[byte]int{}
  for ; right < n; right++ {
  	mp[s[right]]++
      max := getMax(mp)
      // 向右平移不会减小最大子串长度
  	if right-left+1-max > k {
  		mp[s[left]]--
  		left++
  	}
  }

  return right - left
}

func getMax(mp map[byte]int) int{
  res := 0
  for _, v:=range mp{
      if v>res{
          res = v
      }
  }

  return res
}

笔记

这里有个优化，不需要每次都去重新更新max_count。比如说"AAABCDEDFG" k=2，这个case，一开始A出现3次,max_count=3，但是当指针移到D时发现不行了，要移动left指针了。此时count['A']-=1，但是不需要把max_count更新为2。为什么呢？ 因为根据我们的算法，当max_count和k一定时，区间最大长度也就定了。当我们找到一个max_count之后，我们就能说我们找到了一个长度为d=max_count+k的合法区间，所以最终答案一定不小于d。所以，当发现继续向右扩展right不合法的时候，我们不需要不断地右移left，只需要保持区间长度为d向右滑动即可。如果有某个合法区间大于d，一定在某个时刻存在count[t]+1>max_count，这时再去更新max_count即可。

func characterReplacement(s string, k int) int {
  if len(s) <= 1{
      return len(s)
  }
  left, right, n := 0, 0, len(s)
  hm := map[byte]int{}
  maxCount := 0
  ans := 0
  for ;right<n;right++{
      hm[s[right]]++
      maxCount = max(maxCount, hm[s[right]])
      if (right- left + 1) - maxCount > k{
          hm[s[left]]--
          left++
      }
      ans = max(ans, right- left + 1)
  }
  return right - left
}

// Make sure to add code blocks to your code group

1.3.4.最小覆盖子串 (opens new window)

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

笔记

思考一：我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 rrr 指针，和一个用于「收缩」窗口的 lll 指针。在任意时刻，只有一个指针运动，而另一个保持静止。我们在 sss 上滑动窗口，通过移动 rrr 指针不断扩张窗口。当窗口包含 ttt 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口

思考二：如何判断当前的窗口包含所有 ttt 所需的字符呢？我们可以用一个哈希表表示 ttt 中所有的字符以及它们的个数，用一个哈希表动态维护窗口中所有的字符以及它们的个数，如果这个动态表中包含 ttt 的哈希表中的所有字符，并且对应的个数都不小于 ttt 的哈希表中各

class Solution:
  def minWindow(self, s: str, t: str) -> str:

      counter = collections.Counter(t)
      left, right, res, n = 0, 0, " "* (len(s)+1), len(s)
      
      sCounter = collections.defaultdict(int)
      while right < n:
          sCounter[s[right]] += 1
          while self.check(sCounter, counter):
              if len(res) > right-left+1:
                  res = s[left:right+1]
              sCounter[s[left]] -= 1
              left+=1
          right += 1
      return res.replace(" ",  "")

  def check(self, d1: dict, d2: dict) ->bool:
      for k, v in d2.items():
          if k not in d1:
              return False
          if v > d1[k]:
              return False
      return True

// Make sure to add code blocks to your code group

1.3.5无重复字符的最长子串 (opens new window)

给定一个字符串 s ，请你找出其中不含有重复字符的 最长

子串

的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

class Solution:

  def lengthOfLongestSubstring(self, s: str) -> int:
      """
      滑动窗口
      """
      if len(s) < 2:
          return len(s)
      left = 0
      max_len = 0
      occ = set()
      for right in range(len(s)):
          while s[right] in occ:
              occ.remove(s[left])
              left += 1
          if right - left + 1 > max_len:
              max_len = right - left + 1
          occ.add(s[right])
      return max_len

func lengthOfLongestSubstring(s string) int {
  // left := 0
  // max_len := 0
  // hashmap := make(map[rune]bool)
  // for right, c:= range s {
  //     for hashmap[c] == true{
  //         delete(hashmap, rune(s[left]))
  //         left ++
  //     }
  //     hashmap[c] = true
  //     if right - left + 1 > max_len{
  //         max_len = right - left + 1
  //     }
  // }
  // return max_len
  left := 0
  hashMap := make(map[rune] bool)
  max_len := 0
  for right, c := range s {
      for hashMap[c] == true{
          delete(hashMap, rune(s[left]))
          left += 1
      }
      if right - left + 1 > max_len{
          max_len = right - left  + 1
      }
      hashMap[c] = true
  }
  return max_len
}

// Make sure to add code blocks to your code group

最大连续1的个数 III (opens new window)

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

提示：

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1
• 0 <= k <= nums.length

笔记

经过上面的题意转换，我们可知本题是求最大连续子区间，可以使用滑动窗口方法。滑动窗口的限制条件是：窗口内最多有 K 个 0。

class Solution:
  def longestOnes(self, nums: List[int], k: int) -> int:
      ## s[left: right]中num(1)  + num(0) <= k 不断扩大right,当 >k时， 不断收缩left，直到再次满足条件
      left, right = 0, 0
      zeroNum = 0
      ret = 0
      while right < len(nums):
          if nums[right] == 0:
              zeroNum += 1
          while zeroNum > k:
              if nums[left] == 0:
                  zeroNum -= 1
              left += 1
          ret = max(right-left+1, ret)
          right += 1
      return ret
          

func longestOnes(nums []int, k int) int {

  left, right, ret := 0, 0, 0
  zeroNum := 0
  for ;right<len(nums);right++{
      if nums[right] == 0{
          zeroNum++
      }
      for zeroNum >k {
          if nums[left] == 0{
              zeroNum--
          }
          left++
      }
      ret = max(ret, right-left + 1)
  }
  return ret
}

// Make sure to add code blocks to your code group

1.3.6./将 x 减到 0 的最小操作 (opens new window)

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

笔记

// 转化为考虑 移除前缀或者后缀， 移除的sum(前缀)+ sum(后缀) = x

// 等价于 找到一个最长的字串childrenNums，时的sum(childrenNums) = sum(nums) - x

// childrenNums 其实就是去除前后缀后剩下的字串，要想步骤最少，则len(childrenNums)最长

class Solution:
  def minOperations(self, nums: List[int], x: int) -> int:
      x = sum(nums) - x
      left, right = 0, 0
      temp = 0
      ans = inf
      n = len(nums)
      for right, v in enumerate(nums):
          temp += v
          while temp > x and left <=right:
              temp -= nums[left]
              left += 1
          if temp == x:
              ans = min(ans, (n-(right-left+1)))
      return -1 if ans == inf else ans

func minOperations(nums []int, x int) int {

  temp := 0
  for _ , v := range nums{
      temp += v
  }
  x = temp -x
  // 找到一个字串，使得和为x
  ans := 1<<30
  left :=0
  n := len(nums)
  temp = 0
  for right:=0;right<n;right++{
      temp += nums[right]
      for left <=right && temp>x{
          temp -= nums[left]
          left ++
      }
      if temp == x{
          ans = min(ans, n-(right-left+1))
      }
  }
  if ans == 1<<30{
      return -1
  }
  return ans
}

// Make sure to add code blocks to your code group