NarcissusBlog双指针
目录
双指针技巧一般分为两类，一类是快慢指针，一类是左右指针。前者主要解决链表中的问题，比如典型的判断链表中是否有环；后者主要解决数组(或字符串)中的问题，比如二分查找。
快慢指针
快慢指针一般都初始化指向链表头结点head，前进时快指针fast在前，慢指针slow在后。
1、判断链表中是否有环
经典解法就是用两个指针，一个跑得快，一个跑得慢。如果不含有环，跑得快的那个指针最终会遇到null，说明链表不含环；如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环。代码如下：
func hasCycle(head *ListNode) bool {
// 快慢指针
fast, slow := head, head
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
if fast == slow {
return true
}
}
return false
}
2、已知链表有环，返回环的起始位置
第一次相遇，假设慢指针走了k步，那么快指针一定走了2k步，并且多走的k步其实就是fast指针在环里转圈圈，所以k的值就是环长度的整数倍。
接来下，设相遇点距环的起点的距离为m，那么环的起点距头结点head的距离为k - m，也就是说如果从head前进k - m步就能到达环起点。巧的是，如果从相遇点继续前进k - m步，也恰好到达环起点。不管fast在环里到底转了几圈，反正走k步可以到相遇点，那走k - m步一定就是走到环起点了。所以，只要把快慢指针中的任一个重新指向head，然后两个指针同速前进，k - m步后就会相遇，相遇之处就是环的起点了。代码如下：
func detectCycle(head *ListNode) *ListNode {
// 快慢指针
fast, slow := head, head
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
if fast == slow {
break
}
}
// 判断是否有环
if fast == nil || fast.Next == nil {
return nil
}
slow = head
for slow != fast {
fast = fast.Next
slow = slow.Next
}
return slow
}
3、删除链表倒数第n个节点
代码如下：
func removeNthFromEnd(head *ListNode, n int) *ListNode {
// 快慢指针
dummy := &ListNode{}
dummy.Next = head
fast, slow := dummy, dummy
for n != 0 {
fast = fast.Next
n--
}
for fast.Next != nil {
fast = fast.Next
slow = slow.Next
}
// 删除节点
slow.Next = slow.Next.Next
return dummy.Next
}
左右指针
左右指针在数组中实际是指两个索引值，一般初始化为left=0, right = nums.length - 1。常见运用有二分查找和滑动窗口。
1、两数之和
如果数组无序则可以采用哈希表方式，空间复杂度是O(N)。但本题数组有序，可以不需要空间复杂度O(N)，采用双指针技巧。代码如下：
func twoSum(numbers []int, target int) []int {
// 双指针
left, right := 0, len(numbers) - 1
for left < right {
if numbers[left] + numbers[right] == target {
return []int{left + 1, right + 1}
} else if numbers[left] + numbers[right] < target {
left++
} else if numbers[left] + numbers[right] > target {
right--
}
}
return []int{-1, -1}
}
2、反转数组
依然使用左右指针技巧，代码如下：
func reverseString(s []byte) {
// 双指针
left, right := 0, len(s) - 1
for left < right {
s[left], s[right] = s[right], s[left]
left++
right--
}
}
滑动串口
滑动窗口面对找最小问题时，需要缩小窗口(内层用for循环)；面对找最大窗口时，不用缩小窗口(内层用if判断)。滑动窗口模板框架如下：
其中两处...表示跟新窗口数据的地方。
1、最小覆盖子串
滑动窗口算法思路如下：
- 初始化
left=right=0，把索引左闭右开区间[left, right)称为一个窗口。 - 先不断扩大窗口，直到窗口中字符符合要求。
- 此时不断增加
left缩小窗口，直到窗口中字符串不满足要求，同时，每轮缩小前都需要跟新结果。 - 重复以上步骤，直到
right走到s尽头。
思路相当于第2步在寻找可行解，第三步优化可行解，最终找到最优解。
代码如下：
func minWindow(s string, t string) string {
// 滑动窗口
windows, needs := map[byte]int{}, map[byte]int{}
// 表示滑动窗口中满足条件的字符个数
valid := 0
left, right := 0, 0
length, start := len(s) + 1, -1
for _, v := range t {
needs[byte(v)]++
}
for right < len(s) {
// c是将移入窗口的字符
c := s[right]
// 右移窗口
right++
// 窗口内数据跟新
// 滑动窗口windows中只记录需要的字符个数，无关字符不记录
if _, ok := needs[c]; ok {
windows[c]++
if windows[c] == needs[c] {
valid++
}
}
// 判断左窗口是否要收缩
for valid == len(needs) {
// 跟新最小覆盖子串
if right - left < length {
start = left
length = right - left
}
// d是将移出窗口的字符
d := s[left]
left++
// 窗口内数据跟新
if _, ok := needs[d]; ok {
if windows[d] == needs[d] {
valid--
}
windows[d]--
}
}
}
// 返回结果
if length == len(s) + 1 {
return ""
} else {
return s[start : start + length]
}
}
- 代码中
valid变量表示窗口满足needs条件的字符个数，如果和needs长度相同则表示窗口满足条件。 - 因为可能有多个重复字符，因此哈希表值用的数值型而不是布尔型。
2、字符串排列
和上题基本一致，代码如下：
func checkInclusion(s1 string, s2 string) bool {
// 滑动窗口
windows, needs := make([]int, 26), make([]int, 26)
valid, left, right, length := 0, 0, 0, 0
for _, val := range s1 {
needs[int(byte(val) - 'a')]++
// 统计需要满足字符个数
if needs[int(byte(val) - 'a')] == 1 {
length++
}
}
for right < len(s2) {
// 右移窗口
c := int(s2[right] - 'a')
right++
// 跟新窗口数据
if needs[c] != 0 {
windows[c]++
if windows[c] == needs[c] {
valid++
}
}
for valid == length {
// 判断是否满足条件
if right - left == len(s1) {
return true
}
// 左移窗口
d := int(s2[left] - 'a')
left++
// 跟新窗口
if needs[d] != 0 {
if windows[d] == needs[d] {
valid--
}
windows[d]--
}
}
}
return false
}
3、找到字符串中所有字母的异位词
代码如下：
func findAnagrams(s string, p string) []int {
// 滑动窗口
windows, needs := make([]int, 26), make([]int, 26)
valid, left, right, length := 0, 0, 0, 0
var result []int
for _, val := range p {
t := int(byte(val) - 'a')
needs[t]++
if needs[t] == 1 {
length++
}
}
for right < len(s) {
// 右移窗口
c := int(s[right] - 'a')
right++
// 跟新窗口
if needs[c] != 0 {
windows[c]++
if windows[c] == needs[c] {
valid++
}
}
for valid == length {
// 更新结果
if right - left == len(p) {
result = append(result, left)
}
// 左移窗口
d := int(s[left] - 'a')
left++
// 跟新窗口
if needs[d] != 0 {
if windows[d] == needs[d] {
valid--
}
windows[d]--
}
}
}
return result
}
4、最长无重复子串
代码如下：
func lengthOfLongestSubstring(s string) int {
// 滑动窗口
windows := map[byte]int{}
left, right := 0, 0
for right < len(s) {
// 右移窗口
c := s[right]
right++
// 更新窗口
windows[c]++
if right - left > len(windows) {
// 左移窗口
d := s[left]
left++
// 更新窗口
windows[d]--
if windows[d] == 0 {
delete(windows, d)
}
}
}
return right - left
}
注意:本题中是求最大，所以滑动窗口不会缩小，即内层使用
if判断语句而不是循环语句。