一、双指针技巧总结

1、快慢指针

1、判定链表中是否含有环

141.环形链表https://leetcode-cn.com/problems/linked-list-cycle/

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow, fast = head, head
        while fast!=None and fast.next!=None:
            slow = slow.next
            fast=fast.next.next
            if slow == fast:
                return True
        return False

2、已知链表中含有环，返回这个环的起始位置

142.环形链表2https://leetcode-cn.com/problems/linked-list-cycle-ii/

class Solution(object):
    def detectCycle(self, head):
        fast, slow = head, head
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
            if fast == slow:
                break
        slow = head    # 注意这一步
        while fast != slow:  
            fast, slow = fast.next, slow.next
        return slow

3、寻找链表的中点

while fast and fast.next:
    fast, slow = fast.next.next, slow.next
return slow

4、寻找链表的倒数第 k 个元素

√·5、26、删除有序数组中的重复项

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i,j=0,0
        if len(nums)<2: return len(nums)
        for i in range(1,len(nums)):    # 注意 （1，N）
            if nums[i]!=nums[i-1]:    # 注意
                j+=1
                nums[j]=nums[i]
        return j+1

√·6、27. 移除元素

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        j=0
        for i in range(len(nums)):
            if nums[i]!=val:
                nums[j]=nums[i]
                j+=1
        return j

2、左右指针

1、⼆分查找

2、两数之和

3、反转数组

3、不知道什么指针

1、剑指 Offer 24. 反转链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

2、剑指 Offer 25. 合并两个排序的链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        cur = dum = ListNode(0)   # 伪头结点！绝了
        while l1 and l2:
            if l1.val < l2.val:
                cur.next, l1 = l1, l1.next
            else:
                cur.next, l2 = l2, l2.next
            cur = cur.next
        cur.next = l1 if l1 else l2
        return dum.next

√·3、88. 合并两个有序数组(逆序指针)

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        n1=m
        n2=n
        res=m+n-1
        while n1 and n2:
            if nums1[n1-1]<nums2[n2-1]:
                nums1[res]=nums2[n2-1]
                n2-=1
            else:
                nums1[res]=nums1[n1-1]
                n1-=1
            res-=1
        if n2>0: nums1[:n2]=nums2[:n2]

√4、28. 实现 strStr()

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        i,j=0,0
        n=len(needle)
        if n==0 :
            return 0
        while i<len(haystack):
            if haystack[i]==needle[j]:
                j+=1
                n-=1
                i+=1   # 注意
            else:
                i=i-j+1   # 注意
                j=0
                n=len(needle)
            if n==0:
                return i-len(needle)
        return -1

二、滑动窗口

1、最小覆盖子串

2、字符串排列

3、找所有字母异位词

画圈的那个部分，可以保证不包含其他的字符串。
当right-left==t.size 时， 不符合条件，说明含有其他的字符串，这个时候会对左边界进行更新。
但是怎么排除结果和字符是字母一样，顺序不一样呢

4、最长无重复子串

×5、220. 存在重复元素 III

# class Solution:
#     def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
#         for i in range(len(nums)):
#             for j in range(1,k+1):
#                 if i+j<len(nums) and abs(nums[i]-nums[i+j])<=t:
#                     return True
#         return False
class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        from sortedcontainers import SortedSet
        st = SortedSet()
        left, right = 0, 0  
        res = 0
        while right < len(nums):
            if right - left > k:   # 移动窗口
                st.remove(nums[left])
                left += 1
            #  在st中查找nums[right] - t，存在时返回nums[right] - t左侧的位置，不存在返回应该插入的位置.
            index = bisect.bisect_left(st, nums[right] - t)  
            if st and index >= 0 and index < len(st) and abs(st[index] - nums[right]) <= t:
                return True
            st.add(nums[right])
            right += 1
        return False