<aside> 📌 Key Points:

• 什么样的单词或者题型联想到 Two Pointers 解法？
  • maintaining relative order, dedup in sorted array/string，或者given unsorted array但是它的brute force解法是 nlogn以上, 两两比较，谁小移谁，中心开花，array dedup, two sum, manipulate string…
• 要么同向而行(slow/fast)，要么相向而行inward(i/j), 要么中间开花(outward)
• 同向而行(slow/fast pointers)：
  • 典型题型：dedup
  • 两个挡板，三个区域: to-keep: [0, slow), useless: [slow, fast), to-explore:[fast, lastIndex]
  • 基本思想：用两个变量，一个变量记录当前指针的位置(fast)， 另一个变量记录隔板的位置(slow)
  • 处理完毕后，return的结果中，每个integer/char的相对位置不变。
• 相向而行：
  • 典型题型： Two/Three/Four Sum
    • Sort好input：
      • Goal is to find target, or closest to, or smaller/larger than target.
      • 两个指针相向而行 ⇒ 用两个指针遍历去缩小它的range去找到合适的最优解。
      • 怎么移动指针？离target远了，right- - decrease current sum，离taregt太近了，left++ increase current sum
    • 重复元素怎么办？
      • 需要skip重复元素，但是重点是写好logic把所有的元素没有遗漏的搜索 (i.e. 3 Sum)
  • 其他经典题型： water trapped， reverse string，palindrome，
    • Water trapped: find min/max between… Approach: set range to be as min/max as possible first, 谁小移谁，谁大移谁 to find smallest/largest value possible.
• 关键点：每个指针的物理意义要在整个程序运行过程中一直都要保持consistent。每次只要分析当前元素性质是否要加入或者移动slow个班就可以

</aside>

<aside> 🌵 Table of Contents

</aside>

String

Date: July 2, 2023

Problem: Valid Palindrome

Date: July 4, 2023

Problem: Valid Palindrome II

Date: July 4, 2023

Problem: Valid Palindrome III

Date: July 2, 2023

Problem: Minimum Window Substring

Two Sum and Its Derivatives

<aside> ✍️ Two Sum 总结：

• Sort好的input题：
  • goal is to find target or closest/smaller/larger than target.
  • 用两个指针遍历去缩小它的range去找到合适的最优解。⇒ 两个指针相向而行。
  • 怎么移动指针？离target远了，right- - decrease current sum，离taregt太近了，left++ increase current sum
• 重复元素？
  • key就是把所有的元素没有遗漏的找出来 </aside>