LeetCode75学习计划-双指针

算法解题思路很多会借鉴于题解区，如果侵权请联系删除。

本章节知识点为双指针。

移动零

题目标签：

• 数组
• 双指针

题目难度： Easy

题目描述：

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

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

示例：

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

解题思路1：

• 采用双指针的思路，保证左指针左边是非零的数据，即左指针指向非零序列的结束位置，右指针一直向右移动，碰到非零的值与左指针指向的值交换，更新指针位置，知道所有的零值放到最后
• 在双指针移动过程中，如果前边的值都是非零值，会有很多无意义的交换

代码实现：

func moveZeroes(nums []int) {
  // 左右指针位置初始化
  left := 0
  right := 0
  n := len(nums)
  for right < n {
    // 右指针非零值则与左指针交换位置
    if nums[right] != 0 {
      nums[left], nums[right] = nums[right], nums[left]
      // 交换后更新左指针的位置
      left++
    }
    // 更新右指针的位置
    right++
  }
}

解题思路2:

• 不使用双指针来解题了，直接循环并计算零值的数量，如果该值不是零值则根据前边零值的数量与前边的值交换一下位置即可

代码实现2:

func moveZeroes(nums []int)  {
    count := 0
    for i,v := range nums {
    // 如果为0则统计
    if v == 0 {
      count ++
    } else {
      // 如果不为0且前边有0，则根指定位置交换
      // 因为后边的都是0，所以直接补0了
      if count > 0 {
        nums[i-count], nums[i] = v, 0
      }
    }
  }
}

判断子序列

题目标签：

• 字符串
• 动态规划
• 双指针

题目难度： Easy

题目描述：

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

解题思路：

• 指针 i 指向s， 指针 j 指向 t， 如果字符一致则两个指针同时后移，否则则移动 j，遍历完字符串t 之后判断i指针的位置，如果遍历完了字符串 s，则是子序列

代码实现：

func isSubsequence(s string, t string) bool {
  n := len(s)
  m := len(t)
  i := 0
  j := 0
  for i < n && j < m {
    // 匹配成功则i指针后移
    if s[i] == t[j] {
      i ++
    }
    // j指针后移
    j ++
  }
  // i==n则遍历完了字符串s
  return i == n
}

盛水最多的容器

题目标签：

• 贪心
• 数组
• 双指针

题目难度： Medium

题目描述：

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

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

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

解题思路：

• 盛水的多少是由短板决定的
• 双指针指向数组的两侧，盛水量 = 两指针距离 * 短边的高度
• 移动指针的时候移动短板侧的指针，指针收缩后两指针的距离肯定会变小，移动短板的指针才有可能获得最大的盛水量

代码实现：

func maxArea(height []int) int {
  // 双指针
  left := 0
  right := len(height) - 1
  // 存储容量
  maxV := 0
  // 两指针之间必须有距离
  for left < right {
    if height[left] < height[right] {
      maxV = max(maxV, (right - left) * height[left])
      left ++
    } else {
      maxV = max(maxV, (right-left) * height[right])
      right --
    }
  }
  return maxV
}
func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}

K和数对的最大数目

题目标签：

• 哈希表
• 数组
• 双指针

题目难度： Medium

题目描述：

给你一个整数数组 nums 和一个整数 k 。

每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。

返回你可以对数组执行的最大操作数。

解题思路：

• 可以将数组先进行排序，然后采用双指针方法解题最清晰
• 双指针指向数组首尾，如果两个值加起来为 k， 就记录一次，如果小于 k， 则移动首指针，否则移动尾指针

代码实现：

func maxOperations(nums []int, k int) int {
  // 排序
  sort.Ints(nums)
  count := 0
  left := 0
  right := len(nums) - 1
  for left < right {
    // == k 统计一次，更新指针位置
    if nums[left] + nums[right] == k {
      count ++
      left ++
      right --
    // < k 更新左指针
    } else if nums[left] + nums[right] < k {
      left ++
    // > k 更新右指针
    } else {
      right --
    }
  }
  return count
}