知识点

1. 知识点

   1. 双指针技巧：

      1. 什么是双指针技巧

         双指针技巧，两个指针其实是抽象的概念。在数组中，是两个索引；在链表中，是两个临时引用。

      2. 两种双指针

         1. 快慢指针：

            一般用于解决链表的问题，例如：判断链表是否有环、判断链表是否有环并且返回环的起始位置等。

            快慢两个指针，一般初始化都为链表的表头，前进时快指针fast在前，慢指针slow在后。

         2. 左右指针：

            一般用于解决数组的相关问题。例如：二分查找、反转数组、滑动窗口问题

            左右两个指针，一个指向索引为0，一个指向索引为arr.length - 1

   2. 滑动窗口技巧

      1. 什么是滑动窗口技巧

         滑动窗口技巧，是左右指针技巧的巧妙使用。它一般用于字符串匹配类的问题。

      2. 如何使用滑动窗口技巧

         滑动窗口技巧原理是：

         1、初始化left = right = 0，把索引左闭右开区间[left, right)称为一个“窗口”

         2、不断增大right的值，扩大窗口范围，直到找到一个可行解。

         3、停止增加right，转而不断增加left指针缩小窗口，直到窗口范围内，不符合可行解。这一步相当于优化，直到找到最优解。

         4、重复第2和第3步，直到right到边界。

      3. 滑动窗口技巧，子串匹配问题解题思路：

         1. 明确框架

             public String solve(String s, String t) {
             // 将t的字符信息用HashMap存储
             char[] targetCharArr = t.toCharArray();
             HashMap<Character, Integer> need = new HashMap<>();
             for (char c: targetCharArr) 
                 need.put(c, need.getOrDefault(c, 0) + 1);
             // 初始化窗口
             HashMap<Character, Integer> window = new HashMap<>();
            
             // 双指针和计数器
             int left = 0, right = 0;
             int valid = 0;
            
             while (right < s.length()) {
                 // 获取进入窗口的字符
                 char c = s.charAt(right);
                 // 窗口扩大
                 right++;
                 // 进行窗口中数据的更新操作
                 ...
            
                 // 判断是否收缩窗口
                 while (窗口收缩条件) {
                     // 获取出窗口的字符
                     char d = s.charAt(left);
                     // 窗口收缩
                     left++;
                     // 窗口数据更新
                     ...
                 }
            
             }
            }

         2. 思考下列4个问题
            1、扩大窗口后，更新窗口，和哪些数据
            2、什么条件，窗口收缩
            3、窗口收缩后，更新窗口，并且更新哪些数据
            4、我们需要的结果，在扩大窗口时更新还是缩小窗口时更新

   3. Two Sum问题

      对于无序数组，我们一般情况可以考虑：先将数组排序，然后使用双指针技巧实现。

      但是，Two Sum 问题启发我们，对于无序数组，我们同样可以使用哈希表来帮助我们处理

LeetCode算法

2. LeetCode算法

   1. 76.【最小覆盖子串】

      解题思路：

      字符串匹配问题，一般都可以使用滑动窗口技巧。要注意，引用值的比较，使用equals()方法。

   2. 567.【字符串的排列】

      解题思路：

      同样是一个字符串匹配问题，通过滑动窗口技巧来做。

      特别注意，不要将两个if (neet.containsKey())中的语句顺序写反了，第一个需要先将字符放入，然后判断；第二个要先判断，然后将字符从窗口清除出去。

   3. 438.【找到字符串中所有字母异位词】

      解题思路：

      该题同样是一个字符串匹配问题，使用滑动窗口技巧来做

   4. 3.【无重复字符的最长子串】

      解题思路：

      该题也是一个字符串匹配问题，不同点是不需要使用need的HashMap和valid；同时，收缩条件应该是窗口中有重复数据；并且，最关键的，要在收缩窗口完成后更新res，因为窗口收缩的 while 条件是存在重复元素，即收缩完成的窗口才是没有重复元素的。