双指针

二分法常用到左右端点双指针，滑动窗口用到快慢指针和固定间距指针

NO.167 两数相加II
def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1
        while left < right:
            if numbers[left] + numbers[right] > target:
                right -= 1
            elif numbers[left] + numbers[right] < target:
                left += 1
            else:
                return [left + 1, right + 1]
        return []

NO.11 盛水问题
储水能力由短板决定，若改变短板，水槽面积可能增大，若改变长板，水槽面积一定变小。
左右指针分别指向左右两端，每次向内收窄短板，更新面积最大值；直到两针相遇即可获得最大面积
def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1
        res = 0
        while left < right:
            if height[left] < height[right]:
                res = max(res, height[left] * (right - left))
                left += 1
            else:
                res = max(res, height[right] * (right - left))
                right -= 1
        return res
NO.167和NO.11都是左右指针问题

NO.141 环形链表
方法一：哈希法
用set()创建集合，它是一个无序不重复的元素集
如果集合已经在集合里，则存在循环，否则将其添加到集合里，移到下一个节点继续判断
def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False

方法二：快慢指针法
设置一快一慢两个指针，快指针每次前进两步，满指针每次前进一步，如果有环，快慢指针一定会相遇，因为快指针相对于慢指针每次靠近一个节点，因此快慢指针最终会相遇.
快慢指针都从头节点开始，当快指针和快指针的下一个节点都存在时，slow = slow.next, fast = fast.next.next；当fast is slow时，有环
def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow is fast:
                return True
        return False

NO.3 无重复字符串的最长子串
滑动窗口法：如果字符串不存在，返回0；建立集合、左指针、最长子串、现在子串长度，对于字符串里每个字符：现在子串长度先加1，然后判断集合里面是否已经存在，若存在，则移除seen.remove(s[left])，cur_len减1，left + 1
当子串长度大于最大子串时，max_len = cur_len，将i添入到seen里面，最后返回max_len。
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:
    return 0

seen = set()
left = 0
max_len = 0
cur_len = 0

for i in s:
    cur_len += 1
    while i in seen:
        seen.remove(s[left])
        left += 1
        cur_len -= 1
    if cur_len > max_len:
        max_len = cur_len
    seen.add(i)
return max_len
双指针解决字符串、数组、链表相关问题。