刷题笔记0x06：双指针问题
最近在leetcode做了几题双指针题目，来做个总结。
三数之和
题目要求在有n个整数的列表中找出三个数相加刚好为0的所有解。详情见leetcode三数之和。
思路
首先这题暴力穷举是可以解决的，可以把所有组合都试一遍，但显然这样时间复杂度窜到O(n3)了。
试着优化，可以试试用空间换时间，建个哈希表，遍历列表，将直接凑三个数简化为确定一个数，寻找能和它相加为0的两个数。这下时间复杂度降到了O(n2)，空间复杂度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