LeetCode刷题总结

双指针

1.左右指针

左右指针通常在数组有序的情况下，从最小和最大端同时对数组进行处理，对满足特定条件的数组元素进行成对处理，左右指针逐渐靠拢直至发生碰撞，则遍历完所有数组。

应用

1. 从一个有序的数组或链表中，找到一个元素的子集，该子集需要满足某种限制。

2. 对链表、字符串、数组等进行反转

   相关题目

   15. 三数之和：重点是去重

   18. 四数之和：在三数之和的基础上多加一层循环

   

   344. 反转字符串

   剑指 Offer 05. 替换空格

   

   2.快慢指针

   两个指针从同一侧但以不同策略移动的指针。两个指针中有一个移动较快的指针fast和一个较慢的指针slow，当fast指针移动到边界时，停止遍历或进行新一轮遍历。

   应用：多应用于链表

3. 判断链表是否有环，让快慢指针从链表头开始遍历，fast走两步，slow走一步，当fast和slow相遇则表示有环，否则没有。

4. 求一个链表的中间值，fast指针的移动速度是slow指针的两倍，当fast到达链表尾时，slow到达中点。若fast移动x次到达表尾（1+2x）表示有奇数个，直接返回slow的值；若fast到达的是倒数第二个结点，说明有偶数个，则按情况获取中间值。
5. 删除链表倒数第N个值，让fast先移动n步，然后让fast和slow同时移动，当fast指向表尾时，slow指向的就是倒数第N个值。

6. 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

   相关题目

   19. 删除链表的倒数第 N 个结点（3）

   141. 环形链表（1）

   142. 环形链表 II：判断是否有环，有环要找到环的入口

   

   !!! 234. 回文链表(查找链表中点并分割+反转链表+链表比较)

   !!! 143. 重排链表(查找链表中点并分割+反转链表+交错合并链表)

   27. 移除元素（4）

   

   26. 删除有序数组中的重复项（4）

   哈希法

   应用

7. 快速判断数值是否重复出现过。

8. 通过Set进行去重。

9. 数值和下标等需要进行映射的时候。

   相关题目

   1. 两数之和（3）

   454. 四数相加 II（3）

   两数之和和四数相加II都是利用哈希表将当前值存放，通过判断差值是否在哈希表内来取得目标值

   KMP算法

   解题方法

   (1)如何判断是否是回文数组

   回文数：正序读和反序读都是一样的（12321）

   方法一

10. arr数组转为字符串str1

11. arr数组reserve()翻转转为字符串str2

12. 判断str1和str2是否相等

    方法二：双指针

13. left指针指向最左侧，right指针指向最右侧

14. 不断向里比较值是否相等

    (2)对比两个字符串中字母出现次数是否一致

    方法一：暴力法

    方法二：哈希表法

15. 数组也是简单的哈希表，定义一个大小为26的数组record，记录字符串中字符的出现次数

16. 字符a映射为下标0，相应的字符z映射为下标25
17. 利用s[i].charCodeAt()-‘a’.charCodeAt()，计算出字符在数组中的相对位置

18. 遍历s字符串进行++操作，遍历t字符串进行—操作，若record中数值都为0，则表示出现次数一致

    (3)去重的技巧

19. 在数组遍历中，如果当前值等于上一个值，则跳过，因为该数已经做过判断了

20. 当找到某个符合条件的值时，判断后面的数是否和当前值相等，相等则跳过，因为该数也做过判断了

相关题目可看

15. 三数之和