​ 双指针经常在数组和链表中使用。二分查找、滑动窗口、快慢指针都是双指针的变形用法。

二分查找

二分查找，主要是在有序数组中进行查找符合目标值，一般中等难度的问题都不会简单的让查找某个确定的值，而是进行变相的询问，例如询问左边界问题，左边界问题也是用的最多的一种方式。

34. 在排序数组中查找元素的第一个和最后一个位置

这道题可以使用调用两次最左位置，或者是一次最左，一次最右。两次调用最左位置，就是查找$target$和$target+1$的最左位置，这样就可以获得目标值的最左位置和最有位置。当然最右位置等于$target+1$最左位置-1。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func searchRange(nums []int, target int) []int {
    // 时间复杂度的要求所以肯定是使用二分查找方法
    // 我们需要查找的是上边界以及下边界
    if len(nums) == 0 {
        return []int{-1,-1}
    }
    l := binarySearch(nums, target)
    h := binarySearch(nums, target + 1)
    if l < len(nums) && nums[l] == target {
        return []int{l, h-1}
    }
    return []int{-1,-1}
}
func binarySearch(nums []int, target int) int {
    l,h := 0, len(nums)
    for l<h {
        // 由于是查找边界，所以不能是
        mid := l + (h-l)/2
        if nums[mid] >= target {
            h = mid
        } else {
            l = mid + 1
        }
    }
    return l
}

354. 俄罗斯套娃信封问题

这道题可以转换为最长子序列问题，最长子学列问题通常使用动态规划数组，在这里我们使用二分查找的方式来解决最长子序列问题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

func maxEnvelopes(envelopes [][]int) int {
	// 排序之后转换为寻找最长子序列问题
	sort.Slice(envelopes, func(i, j int) bool {
		if envelopes[i][0] == envelopes[j][0] {
			return envelopes[i][1] > envelopes[j][1]
		}
		return envelopes[i][0] < envelopes[j][0]
	})
	n := len(envelopes)
	heights := make([]int, n)
	for i := 0; i < n; i++ {
		heights[i] = envelopes[i][1]
	}
	//求heights里面的最长上升子学列
	var lengthOfLTS func() int
	//
	lengthOfLTS = func() int {
		// 洗牌算法
		piles := 0
		top := make([]int, n)
		for i := 0; i < n; i++ {
			// 当前要处理的扑克牌
			poker := heights[i]
			// piles表示此时的牌堆
			// 而left就是当前要处理的牌要插入的位置，如果位置大于piles
			// 说明是放在牌堆大小扩充了
			left, right := 0, piles
			for left < right {
				mid := left + (right-left)/2
				if top[mid] >= poker {
					right = mid
				} else {
					left = mid + 1
				}
			}
			if left == piles {
				piles++
			}
			top[left] = poker
		}
		return piles
	}
	return lengthOfLTS()
}

875. 爱吃香蕉的珂珂

这道题是二分搜索的应用，将问题抽象为二分搜索。即我们要寻找一个$x$，使得$f(x)$满足目标$target$。

例如该题中：$x$为吃香蕉的速度，$f(x)$为判断以$x$速度吃香蕉是否可以在警卫回来之前吃完($target$)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

func minEatingSpeed(piles []int, h int) int {
	// 首先确定速度k的范围
	// k最小值为1， 最大值当没办法进行确定的时候，就可以选择值的最大可能性
	// 二分法寻找左边界问题
	l, r := 1, 100000001
	sort2.Ints(piles)
	var f func(x int) bool
    // f(x)
	f = func(x int) bool {
		use := 0
		for i := 0; i < len(piles); i++ {
			use += piles[i] / x
			if piles[i]%x != 0 {
				use++
			}
		}
		return use <= h
	}
	for l < r {
		mid := l + (r-l)/2
		if f(mid) {
			// 可以吃完
			r = mid
		} else {
			// 不可以吃完
			l = mid + 1
		}
	}
	return l
}

滑动窗口

滑动窗口算法是双指针的一种变种，或者说是应用方法。我们一般考虑的就是窗口的两个端点，可以看作两个指针。一般应用的题型的数据结构是字符串或者是数组。而且滑动窗口算法一般都可以使用暴力法来进行解决。

滑动窗口一般处理都是连续问题，连续子数组或者是子串问题。因为非连续问题不可能存在于一个窗口中，那个时候可能使用动态规划可能会好一点。从类型上来说，滑动窗口一般分为两种类型：

  • 固定窗口大小，然后找到符合条件的结果
  • 非固定窗口大小，找到满足符合条件的结果。

固定窗口大小

对于固定窗口大小，我们第一步就需要初始化窗口，即构建一个最开始窗口。

  • 初始化l为0，初始化r使得r-l+1为窗口大小。
  • 同时移动l、r，来保证窗口的移动。
  • 判断窗口内部是否满足题目的条件，如果满足则更新或者直接结束，不满足则继续进行循环。
例题

438. 找到字符串中所有字母异位词 - 力扣（LeetCode） (leetcode-cn.com)

该题就是固定窗口大小，而窗口大小并不是直接给出，而是根据匹配字符串的长度来确定窗口长度大小。使用哈希表的目的是为了判断是否满足题目中的条件，而答题流程则是固定滑动窗口答题流程。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func findAnagrams(s, p string) (ans []int) {
	sLen, pLen := len(s), len(p)
	if sLen < pLen {
		return
	}

	var sCount, pCount [26]int
    // 这部分就是初始化滑动窗口
	for i, ch := range p {
		sCount[s[i]-'a']++
		pCount[ch-'a']++
	}
    // 初始化之后就需要进行一次判断
	if sCount == pCount {
		ans = append(ans, 0)
	}
	for i, ch := range s[:sLen-pLen] {
		// 进入滑动窗口 即r的移动
		sCount[ch-'a']--
		// 从滑动窗口中取出  即l的移动
		sCount[s[i+pLen]-'a']++
        // 进行是否满足条件的判断
		if sCount == pCount {
			ans = append(ans, i+1)
		}
	}
	return
}

可变滑动窗口

对于可变滑动窗口，由于窗口大小是未知的，所以初始化的时候窗口大小为1

  • 初始化l、r为0
  • 移动r，来保证窗口的扩张。
  • 判断窗口内部是否满足题目的条件，如果满足则更新或者直接结束，不满足则可以通过和条件对比来增加l或者是r。
例题

713. 乘积小于K的子数组 - 力扣（LeetCode） (leetcode-cn.com)

该题就很明显可以使用滑动窗口，并且窗口大小是可变的。而需要满足的条件就是乘积小于K。之后每次满足条件之后更新参数即可，并根据乘积值来更新窗口的大小。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func numSubarrayProductLessThanK(nums []int, k int) int {
    // 乘积小于k
    // 连续的子数组
    // 严格小于 等于不行
    // 正整数数组，即 k<=1的话就直接返回空数组
    res := 0
    if k <= 1{
        return res
    }
    mul := 1
    l,r := 0,0
    // 滑动窗口 窗口长度的变化
    // 如果一个窗口的乘积小于k 因为都是正整数 所以整个区间内部的小窗口都会小于k
    for r < len(nums) {
        mul *= nums[r]
        r++
        for mul >= k {
            mul /= nums[l]
            l++
        }
        res += (r-l)
    }
    return res
}

快慢指针

快慢指针一般用于在链表中寻找中点，或者是链表环问题。一般是利用快指针会比慢指针走的距离多一倍。

142. 环形链表 II

相比环形链表该题需要找到环的入口，判断环形链表则是使用快指针慢指针走的位置是存在倍数关系的。而判断环的入口则是使用了两者之间走过的距离差是环的长度整数倍的数学关系。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func detectCycle(head *ListNode) *ListNode {
    // 找到环入口节点
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if fast == slow {
            break
        }
    }
    if fast == nil || fast.Next == nil {
        return nil
    }
    // 相等证明有环
    fast = head
    for slow != fast {
        slow = slow.Next
        fast = fast.Next
    }
    return fast
}

876. 链表的中间结点

该题是快慢指针最简单的运用，即快指针比慢指针走的距离的二倍。

1
2
3
4
5
6
7
8

func findMid(head *ListNode) *ListNode{
    slow,fast := head,head
    for fast!=nil || fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}