常用算法 — 双指针

双指针有时也叫滑动窗口，如果一定要和滑动窗口区别，那就是滑动窗口的窗口一般是向一个方向滑动，而双指针一般强调左右两个指针。除此之外，可能还会单独强调快慢指针，快慢指针也是一种双指针，但是两个指针的运动速度是不一样的，一快一慢。

左右指针 #

二分查找 #

二分查找算法需要使用左右（或高低）两个指针（或索引）在已经排序的链表（或数组）上来实现。详见二分查找专题。

167. 两数之和 II - 输入有序数组除了双指针，更优秀的办法就是使用二分查找，将时间复杂度从 $ O(n) $ 降到 $O(nlogn)$ 。

var twoSum = function(numbers, target) {
    for (let i = 0; i < numbers.length; i++) {
        let low = i + 1
        let high = numbers.length - 1
        while (low <= high) {
            let mid = Math.floor((high - low) / 2) + low
            if (numbers[mid] + numbers[i] == target) {
                return [i+1, mid+1]
            } else if (numbers[mid]+numbers[i] > target) {
                high = mid - 1
            } else {
                low = mid + 1
            }
        }
    }
    return [-1, -1]
};

回文字符串 #

344. 反转字符串

var reverseString = function(s) {
    let left = 0
    let right = s.length - 1
    while (left < right) {
        let temp = s[left]
        s[left] = s[right]
        s[right] = temp
        left++
        right--
    }
};

快慢指针 #

链表问题 #

141. 环形链表

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
    slow, fast := head, head.Next
    for fast != slow {
        if fast == nil || fast.Next == nil {
            return false
        }
        slow = slow.Next
        fast = fast.Next.Next
    }
    return true
}

数组问题 ✨ #

个人觉得快慢指针在数组中的应用都比较巧妙，很难自己想到，可以多做几个题体会。

26. 删除有序数组中的重复项

var removeDuplicates = function(nums) {
    if (nums.length <=1) {
        return nums.length
    }
    let fast = 1
    let slow = 1
    while (fast < nums.length) {
        if (nums[fast] !== nums[fast -1]) {
            nums[slow] = nums[fast]
            slow ++
        }
        fast ++
    }
    return slow
}

27. 移除元素代码几乎一样，只是需要注意一下边界。

var removeElement = function(nums, val) {
    let fast = 0
    let slow = 0
    while (fast < nums.length) {
        if (nums[fast] !== val) {
            nums[slow] = nums[fast]
            slow++
        }
        fast++
    }
    return slow
};

可能还需要交换双指针的值 283. 移动零

var moveZeroes = function(nums) {
    if (nums.length <= 1){
        return nums
    }
    let fast = 0
    let slow = 0
    while (fast < nums.length) {
        if (nums[fast] !== 0) {
            let temp = nums[slow]
            nums[slow] = nums[fast]
            nums[fast] = temp
            slow ++
        }
        fast ++
    }
    return nums
};

前后指针 #

链表专题已经提到过，前后指针区别于快慢指针，两个指针步伐通常一致。

19. 删除链表的倒数第 N 个结点

var removeNthFromEnd = function(head, n) {
    let tail = head
    let dummy = new ListNode(0, head)
    let prev = dummy

    for (let i = 0; i < n; i ++) {
        tail = tail.next
    }

    while (tail !== null) {
        tail = tail.next
        prev = prev.next
    }

    prev.next = prev.next.next
    return dummy.next
};

总结 #

子串、数组、链表问题都可以优先考虑双指针，如果想不出来，那一定不是双指针的问题。