双指针法有三种：
左右指针法
左右指针法是最常见的双指针法，左右两头两个指针相向而行。一样寻常针对有序数组找目标值有奇效，经典的题目案例就是多数之和。
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 > 0 { break } // 去重，如果与前一个数雷同，则直接跳过这一次不须要处理惩罚 if i > 0 && nums == nums[i-1] { continue } var left = i + 1, right = nums.count - 1// 界说左右指针 //开始左右夹逼，如果三数之和小于0，则left往右移1，大于0则right往左移1 while left < right { let result = nums + nums[left] + nums[right] if result == 0 { ans.append([nums, 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 }}滑动窗口有模板，碰到雷同题目都可套用模板。 |
