双指针及滑动窗口类题目总结

今天药忘吃喽~ 2022-09-07 05:54 121阅读 0赞

### 双指针及滑动窗口类题目总结 ###

*  双指针
 *   *   *  情景一
         *   *   *  Leetcode相关题目
         *  情景二
         *   *   *  Leetcode相关题目

# 双指针 #

### 情景一 ###

我们通过迭代数组来解决一些问题。通常，我们只需要一个指针进行迭代，即从数组中的第一个元素开始，最后一个元素结束。然而，有时我们会使用`两个指针`进行迭代。

**经典案例**：

> 反转数组中的元素。比如数组为 `['l', 'e', 'e', 't', 'c', 'o', 'd', 'e']`，反转之后变为`['e', 'd', 'o', 'c', 't', 'e', 'e', 'l']`。

使用双指针技巧，其思想是分别将两个指针分别指向数组的开头及末尾，然后将其指向的元素进行交换，再将指针向中间移动一步，继续交换，直到这两个指针相遇。

def reverseString(self, s):
        i, j = 0, len(s) - 1
        while i < j:
            s[i], s[j] = s[j], s[i]
            i += 1
            j -= 1

**小结**：

我们来总结一下，使用双指针的典型场景之一是你想要

> 从两端向中间迭代数组。

这时你可以使用双指针技巧：

> 一个指针从头部开始，而另一个指针从尾部开始。

这种技巧经常在排序数组中使用。

##### Leetcode相关题目 #####

<table> 
 <thead> 
  <tr> 
   <th align="left">题目</th> 
   <th align="center">方法</th> 
   <th align="center">Java代码</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left"><a href="https://leetcode-cn.com/problems/reverse-string/" rel="nofollow">344. 反转字符串</a></td> 
   <td align="center">双指针</td> 
   <td align="center"><a href="https://blog.csdn.net/weixin_43999327/article/details/119852248" rel="nofollow">戳我</a></td> 
  </tr> 
  <tr> 
   <td align="left"><a href="https://leetcode-cn.com/problems/array-partition-i/" rel="nofollow">561. 数组拆分 I</a></td> 
   <td align="center">双指针</td> 
   <td align="center"><a href="https://blog.csdn.net/weixin_43999327/article/details/119852340" rel="nofollow">戳我</a></td> 
  </tr> 
  <tr> 
   <td align="left"><a href="https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/" rel="nofollow">167. 两数之和 II - 输入有序数组</a></td> 
   <td align="center">双指针</td> 
   <td align="center"><a href="https://blog.csdn.net/weixin_43999327/article/details/119852391" rel="nofollow">戳我</a></td> 
  </tr> 
 </tbody> 
</table>

### 情景二 ###

有时，我们可以使用两个`不同步`的指针来解决问题，即快慢指针。与情景一不同的是，两个指针的运动方向是相同的，而非相反。

**经典问题:**

> 给你一个数组`nums`和一个值`val`，你需要 原地 移除所有数值等于`val`的元素，并返回移除后数组的新长度。

如果我们没有空间复杂度上的限制，那就更容易了。我们可以初始化一个新的数组来存储答案。如果元素不等于给定的目标值，则迭代原始数组并将元素添加到新的数组中。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw_size_16_color_FFFFFF_t_70]  
实际上，它相当于使用了两个指针，一个用于原始数组的迭代，另一个总是指向新数组的最后一个位置。

##### Leetcode相关题目 #####

<table> 
 <thead> 
  <tr> 
   <th align="left">题目</th> 
   <th align="center">方法</th> 
   <th align="center">Java代码</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left"><a href="https://leetcode-cn.com/problems/remove-element/" rel="nofollow">27. 移除元素</a></td> 
   <td align="center">双指针</td> 
   <td align="center"><a href="https://blog.csdn.net/weixin_43999327/article/details/119852466" rel="nofollow">戳我</a></td> 
  </tr> 
  <tr> 
   <td align="left"><a href="https://leetcode-cn.com/problems/max-consecutive-ones/" rel="nofollow">485. 最大连续 1 的个数</a></td> 
   <td align="center">双指针</td> 
   <td align="center"><a href="https://blog.csdn.net/weixin_43999327/article/details/119852622" rel="nofollow">戳我</a></td> 
  </tr> 
  <tr> 
   <td align="left"><a href="https://leetcode-cn.com/problems/minimum-size-subarray-sum/" rel="nofollow">209. 长度最小的子数组</a></td> 
   <td align="center">双指针、滑动窗口</td> 
   <td align="center"><a href="https://blog.csdn.net/weixin_43999327/article/details/119852531" rel="nofollow">戳我</a></td> 
  </tr> 
 </tbody> 
</table>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk5OTMyNw_size_16_color_FFFFFF_t_70]: /images/20220829/c4ed8b0fce1f43ad8fdaec0f6235d5c7.png