【第十天 - Two-pointer 介绍】

Q1. Two-pointer 是什麽?

• 我个人认为双指标 ( Two-pointer ) 比较像写题目的技巧，一些演算法也会用到双指标的概念，例如昨天介绍到的 Quick Sort，就有使用到双指标的技巧
  • 双指标主要可以分为两种：

    • 快慢指标：两个指标一起指向头，或是一起指向尾，一个指标可能是按着顺序走访，一个是根据问题的需求来移动，让指标会有快慢之分，他们都会一起向右移动，也称为同向指标，类似 Quick Sort 的 Lomuto
      

    • 左右指标：两个指标一个指向头，一个指向尾，k 会向右移动，j 向左移动，两个指标会逐渐靠近，也称为反向指标，类似 Quick Sort 的 Hoare
      

Q2. 学会 Two-pointer 概念可以做什麽 ?

• 可以在以下情境考虑 Two pointer：
  • 题目禁止使用额外空间，原地交换值、比较
  • 题目给已经排序过的资料，然後对此资料进行一些操作，例如删掉重复的元素等...
• 双指标可以分为两种：

  1. 快慢指标可以解决：

     • 将已经排序过的资料，把重复的元素删掉

       

     • 判断 linked list 是否有环，若是两个指标相遇，代表有环

     

  2. 左右指标可以解决的题目类型：

     1. 反转阵列，把 k 与 j 值交换

        

     2. 检查 string 是否回文，检查 k 位置的值 是否等於 j 位置的值

        

     3. 在已经排序过的资料中，题目会给一个 target ，找出资料中哪两个数字相加为 target

        

     4. Quick Sort 的 Hoare 方法就是使用左右指标的概念将数字进行排序

        

Lab. 明天要解的题目：

• 明天要解的题目有两题，分别是：
  • 26. Remove Duplicates from Sorted Array
  • 167. Two Sum II - Input array is sorted

26. Remove Duplicates from Sorted Array

• 题目连结：https://leetcode.com/problems/valid-parentheses/

• 题目叙述：

  • 题目会给你一个从小排序到大的资料，但是里面有重复的元素，你需要把他删掉
  • 有些语言是不能把资料里的元素删掉 ( array 长度不能被改变)，所以你需要把後面所有元素往前平移
  • 不过我们这边使用的是 python，可以删除任意位置的元素 ，所以只要遇到多余的就删掉即可，并且回传删完重复元素後的资料长度

  

• 测资的 Input/Output

  • 题目如果给你 [1,1,2] 那你要把多余的元素删掉，删完重复元素後的资料长度

    

• 题目的条件

  • nums 里的资料，会有 0~ 30000 个
  • 每一笔资料都会介於 -100~100
  • nums 里的资料是经过排序的 (从小排到大)

  

167. Two Sum II - Input array is sorted

• 题目连结：https://leetcode.com/problems/valid-parentheses/

• 题目叙述：

  • 题目会给你一个从小排序到大的资料，跟希望找到的两数相加的和 (target)

  • 你需要找出哪两个位置的值，相加会等於 target

  • 哪两个位置的值相加为 target，只会有一种答案

  • 同一个元素不能加两次

    

• 测资的 Input/Output

  • 题目会给你一个递增的数列，跟希望找到的目标总和 (target)

  • 回传一个 list 结构的资料，里面要包含相加会等於 target 的 index

    

• 题目的条件

  • 资料长度为 2~30000

  • 每一笔资料介於 -1000~1000

  • 资料由小排序到大

  • 相加的目标 (target) 介於 -1000~1000

  • 只会有唯一解