双指针法有三种：
- 左右指针法（头尾指针法）
- 快慢指针法
- 滑动窗口
左右指针法
左右指针法是最常见的双指针法，左右两端两个指针相向而行。一般针对有序数组找目标值有奇效，经典的题目案例就是多数之和。
N数之和的问题如果用朴素解法（暴力解法）时间复杂度肯定为O(n^N)。(n位数数组元素的个人，N为N个数之和)
当然还有不少类似问题能用双指针法，比如反转数组等，不一一举例。举例一道中等的三数之和吧。
三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
class Solution {
func threeSum(_ nums: [Int]) -> [[Int]] {
var ans = [[Int]]()
if nums.count < 3 {
return ans
}
let nums = nums.sorted() // 排序，对有序数组才有效
for i in 0 ... nums.count - 3 {
// 因为是从小到大有序数组，所以这个数大于0，后面的数都比他大因此肯定和大于0且直接break跳出循环
if nums[i] > 0 {
break
}
// 去重，如果与前一个数相同，则直接跳过这一次不需要处理
if i > 0 && nums[i] == nums[i-1] {
continue
}
var left = i + 1, right = nums.count - 1// 定义左右指针
//开始左右夹逼，如果三数之和小于0，则left往右移1，大于0则right往左移1
while left < right {
let result = nums[i] + nums[left] + nums[right]
if result == 0 {
ans.append([nums[i], nums[left], nums[right]])
//跳过第二第三个数相同的结果
repeat {
left += 1
} while left < right && nums[left] == nums[left - 1]
repeat {
right -= 1
} while left < right && nums[right] == nums[right + 1]
} else if result < 0 {
//跳过第二个数相同的结果
repeat {
left += 1
} while left < right && nums[left] == nums[left - 1]
} else {
//跳过第三个数相同的结果
repeat {
right -= 1
} while left < right && nums[right] == nums[right + 1]
}
}
}
return ans
}
}
此题需要注意的是两点
- 要有序数组，因此一开始要对数组进行排序，这样我们才可以运用左右指针。如果result小于0，则需要增大第二个数，则left往右移动一格；如果result大于0，则需要减少第三个数，则right往左移动一格；result等于0，则三数字加入answer数组。
- 去重，如果在结果中去重会相对麻烦，而且增加了上一步骤遍历的次数，因此需要在遍历的初期就进行检查去重，比如第一个数与上一次第一个数相同则continue跳过此次等。详见题解代码中的注释。
快慢指针法
快慢指针是一个很巧妙的方法，对于链表操作有奇效，可以用来找链表的中点，也可以用来证明环形链表。
链表的中间结点
题目：给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
class Solution {
func middleNode(_ head: ListNode?) -> ListNode? {
if head?.next == nil {
return head
}
var slow = head
var fast = head
while fast?.next != nil {
slow = slow?.next
fast = fast?.next?.next
}
return slow
}
}
此题使用快慢指针，慢的取next，快的取next.next，快指针取完的时候慢指针会停留在中间节点。
环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
class Solution {
func hasCycle(_ head: ListNode?) -> Bool {
var slow: ListNode? = head
var fast: ListNode? = head
while fast?.next != nil {
slow = slow?.next
fast = fast?.next?.next
if slow === fast{
return true
}
}
return false
}
}
此题使用快慢指针，快指针最终与慢指针重合那说明是环形链表。
滑动窗口
之所以成为滑动窗口，是因为左右指针形成了一个范围，就像窗口一样，往前滑动。
一般子串问题全靠它，一前一后齐头并进。
找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
class Solution {
func findAnagrams(_ s: String, _ p: String) -> [Int] {
let arrS = Array(s), arrP = Array(p)
var need = [Character: Int](), window = [Character: Int]()
for c in arrP {
need[c, default: 0] += 1
}
var left = 0, right = 0
var valid = 0
var ans = [Int]()
while right < arrS.count {
let c = arrS[right]
right += 1
// 进行窗口内数据的一系列更新
if need.keys.contains(c) {
window[c, default: 0] += 1
if window[c] == need[c] {
valid += 1
}
}
// 判断左侧窗口是否要收缩
while right - left >= arrP.count {
// 当窗口符合条件时，把起始索引加入 ans
if valid == need.count {
ans.append(left)
}
let d = arrS[left]
left += 1
if need.keys.contains(d) {
if window[d] == need[d] {
valid -= 1
}
window[d, default: 1] -= 1
}
}
}
return ans
}
}
滑动窗口有模板，遇到类似问题都可套用模板。
网友评论