前情提示:Go語言學習者。本文參考https://labuladong.gitee.io/algo,代碼自己參考抒寫,若有不妥之處,感謝指正
關于golang算法文章,為了便于下載下傳和整理,都已開源放在:
- https://github.com/honlu/GoLabuladongAlgorithm
-
https://gitee.com/dreamzll/GoLabuladongAlgorithm
友善就請分享,star!備注轉載位址!歡迎一起學習和交流!
涉及題目
Leetcode 141.環形連結清單
Leetcode 142.環形連結清單II
Leetcode 704. 二分查找
Leetcode 167.兩數之和 II - 輸入有序數組
正文
我把雙指針技巧再分為兩類,一類是「快慢指針」,一類是「左右指針」。前者解決主要解決連結清單中的問題,比如典型的判定連結清單中是否包含環;後者主要解決數組(或者字元串)中的問題,比如二分查找。
一、快慢指針的常見算法
快慢指針一般都初始化指向連結清單的頭結點 head,前進時快指針 fast 在前,慢指針 slow 在後,巧妙解決一些連結清單中的問題。
1、判定連結清單中是否含有環
這應該屬于連結清單最基本的操作了,如果讀者已經知道這個技巧,可以跳過。
單連結清單的特點是每個節點隻知道下一個節點,是以一個指針的話無法判斷連結清單中是否含有環的。
如果連結清單中不含環,那麼這個指針最終會遇到空指針 null 表示連結清單到頭了,這還好說,可以判斷該連結清單不含環。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func hasCycle(head *ListNode) bool{
for head != nil{
head = head.Next
}
return false
}
但是如果連結清單中含有環,那麼這個指針就會陷入死循環,因為環形數組中沒有 null 指針作為尾部節點。
經典解法就是用兩個指針,一個跑得快,一個跑得慢。如果不含有環,跑得快的那個指針最終會遇到 null,說明連結清單不含環;如果含有環,快指針最終會超慢指針一圈,和慢指針相遇,說明連結清單含有環。
/** 141
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func hasCycle(head *ListNode) bool {
var fast, slow *ListNode
fast = head
slow = head
for fast != nil && fast.Next != nil{
fast = fast.Next.Next
slow = slow.Next
if fast == slow{
return true
}
}
return false
}
2、已知連結清單中含有環,傳回這個環的起始位置
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnLx8CX4gTJykTJ5UUJ3gTJDhTJ2UUJDhTJGhTJ1UUJvw1clJXd0NWaw9CXyVGdzFWbvw1dhJ3Lc1Ga0lmcvdGbh1yZul2ajVnZvw1Zu9GZhxWdiFGbvwVbvNmLlVGdpd2Lc9CX6MHc0RHaiojIsJye.png)
這個問題一點都不困難,有點類似腦筋急轉彎,先直接看代碼:
// 142
func detectCycle(head *ListNode) *ListNode{
var fast, slow *ListNode
fast = head
slow = head
for fast != nil && fast.Next != nil{
fast = fast.Next.Next
slow = slow.Next
if fast == slow{
break
}
}
// 上面的代碼類似 hasCycle函數
if fast == nil || fast.Next == nil{
// fast 遇到空指針說明沒有環
return nil
}
slow = head
for slow != fast{
fast = fast.Next
slow = slow.Next
}
return slow
}
可以看到,當快慢指針相遇時,讓其中任一個指針指向頭節點,然後讓它倆以相同速度前進,再次相遇時所在的節點位置就是環開始的位置。這是為什麼呢?
第一次相遇時,假設慢指針 slow 走了 k 步,那麼快指針 fast 一定走了 2k 步,也就是說比 slow 多走了 k 步(也就是環的長度)。
設相遇點距環的起點的距離為 m,那麼環的起點距頭結點 head 的距離為 k - m,也就是說如果從 head 前進 k - m 步就能到達環起點。
巧的是,如果從相遇點繼續前進 k - m 步,也恰好到達環起點。
是以,隻要我們把快慢指針中的任一個重新指向 head,然後兩個指針同速前進,k - m 步後就會相遇,相遇之處就是環的起點了。
3、尋找連結清單的中點
類似上面的思路,我們還可以讓快指針一次前進兩步,慢指針一次前進一步,當快指針到達連結清單盡頭時,慢指針就處于連結清單的中間位置。
for fast != nil && fast.next != nil{
fast = fast.next.next
slow = slow.next
}
// slow 就在中間位置
return slow
當連結清單的長度是奇數時,slow 恰巧停在中點位置;如果長度是偶數,slow 最終的位置是中間偏右:
尋找連結清單中點的一個重要作用是對連結清單進行歸并排序。
回想數組的歸并排序:求中點索引遞歸地把數組二分,最後合并兩個有序數組。對于連結清單,合并兩個有序連結清單是很簡單的,難點就在于二分。
但是現在你學會了找到連結清單的中點,就能實作連結清單的二分了。關于歸并排序的具體内容本文就不具體展開了。
4、尋找連結清單的倒數第 k 個元素
我們的思路還是使用快慢指針,讓快指針先走 k 步,然後快慢指針開始同速前進。這樣當快指針走到連結清單末尾 null 時,慢指針所在的位置就是倒數第 k 個連結清單節點(為了簡化,假設 k 不會超過連結清單長度):
var slow,fast *ListNode
slow = fast = head
for k-- > 0{
fast = fast.next
}
for fast != nil{
slow = slow.next
fast = fast.next
}
return slow
二、左右指針的常用算法
左右指針在數組中實際是指兩個索引值,一般初始化為 left = 0, right = nums.length - 1 。
1、二分查找
前文「二分查找」有詳細講解,這裡隻寫最簡單的二分算法,旨在突出它的雙指針特性:
// 704
func search(nums []int, target int) int{
left := 0
right := len(nums) - 1
for left <= right{
mid := (right + left) / 2
if nums[mid] == target{
return mid
}else if nums[mid] < target{
left = mid + 1
}else{
right = mid -1
}
}
return -1
}
2、兩數之和
直接看一道 LeetCode 題目吧:
隻要數組有序,就應該想到雙指針技巧。這道題的解法有點類似二分查找,通過調節 left 和 right 可以調整 sum 的大小:
// 167
func twoSum(numbers []int, target int) []int {
// 左右指針在數組的兩端初始化
left := 0
right := len(numbers)-1
for left < right{
sum := numbers[left] + numbers[right]
if sum == target{
// 題目要求的索引是從1開始的
return []int{left+1, right+1}
}else if sum < target{
left++ // 讓sum大一點
}else{
right-- // 讓sum小一點
}
}
return []int{-1, -1}
}
3、反轉數組
func reverse(nums []int){
left := 0
right := len(nums) - 1
for left < right{
// 交換nums[left]和nums[right]
temp := nums[left]
nums[left] = nums[right]
nums[right] = temp
left++
right--
}
}
4、滑動視窗算法
這也許是雙指針技巧的最高境界了,如果掌握了此算法,可以解決一大類子字元串比對的問題,不過「滑動視窗」稍微比上述的這些算法複雜些。
幸運的是,這類算法是有架構模闆的,将在後面講解了「滑動視窗」算法模闆,幫大家秒殺幾道 LeetCode 子串比對的問題。