刷题笔记0x06：双指针问题

最近在leetcode做了几题双指针题目，来做个总结。

三数之和

题目要求在有n个整数的列表中找出三个数相加刚好为0的所有解。详情见leetcode三数之和。

思路

首先这题暴力穷举是可以解决的，可以把所有组合都试一遍，但显然这样时间复杂度窜到O(n³)了。

试着优化，可以试试用空间换时间，建个哈希表，遍历列表，将直接凑三个数简化为确定一个数，寻找能和它相加为0的两个数。这下时间复杂度降到了O(n²)，空间复杂度O(n)。

别急，还可以想想办法节省空间。这里利用一下排序。先将整个列表按升序排序，对于这个排好序的列表而言：

• 某个元素nums[i]如果大于0，那么就可以直接返回了，因为是按升序排序的，后面的数只会更大，不可能相加等于0。
• 当前值nums[i],使左指针L为i+1，右指针R为len(nums) - 1。三个数相加，等于0就保存结果，大于0，那么右边值太大，R减一，反过来，小于0，左边值太小，L加一。

思路有了，剩下的就是可能还有一些重复值要去掉，避免重复计算，以及列表长度过小的情况。

具体代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n=len(nums)
        res=[]
        if not nums or n < 3:
            return []
        nums.sort()
        res=[]
        for i in range(n):
            if nums[i] > 0:
                return res
            if i > 0 and nums[i] == nums[i-1]:
                continue
            L=i+1
            R=n-1
            while L < R:
                if nums[i] + nums[L] + nums[R] == 0:
                    res.append([nums[i], nums[L], nums[R]])
                    while L < R and nums[L] == nums[L+1]:
                        L=L+1
                    while L < R and nums[R] == nums[R-1]:
                        R=R-1
                    L=L+1
                    R=R-1
                elif nums[i] + nums[L] + nums[R] > 0:
                    R=R-1
                else:
                    L=L+1
        return res

相似题目

leetcode上还有个最接近的三数之和与四数之和，思路都差不多，可以去尝试一下。

删除链表倒数第N个节点

题目要求给定链表与要n，删去倒数第n个元素并且返回链表头。详情见删除链表的倒数第N个节点

思路

这个问题首先想到双指针解决，建立slow和fast两个指针。

• 两个指针都指向链表头部，让fast先跑n步，然后两个指针再一起跑。
• fast到末尾时，slow刚好就是倒数第n+1个元素。让slow.next指向倒数第n-1，也就是slow.next = slow.next.next，即完成删除。
• 注意在让fast先走n步过程中，如果fast.next存在，则fast前进直到前进n步为止，否则fast.next不存在就返回head.next。这么做的原因是存在链表长度为n，要求删除倒数第n的情况。

具体代码

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        if not head or not head.next:
            return None
        fast, slow = head, head
        for i in range(n):
            if fast.next:
                fast = fast.next
            else:
                return head.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return head