左右指针法

左右指针法是最常见的双指针法，左右两端两个指针相向而行。一般针对有序数组找目标值有奇效，经典的题目案例就是多数之和。
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
    }
}

滑动窗口有模板，遇到类似问题都可套用模板。

双指针法（Swift代码篇）

双指针法（Swift代码篇）

左右指针法

快慢指针法

滑动窗口