Leetcode——玩转双指针

分手后的思念是犯贱 2023-01-10 15:58 180阅读 0赞

**目录**

双指针初识

Two Sum

归并两个有序数组

快慢指针

数学 + 双指针

哈希

--------------------

# 双指针初识 #

*  双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延伸到多个数组的多个指针。
 *  若两个指针指向同一数组，遍历方向相同且不会相交，则也称为滑动窗口(两个指针包围的区域即为当前的窗口),经常用于区间搜索。
 *  若两个指针指向同一数组，但是遍历方向相反，则可以用来进行搜索，待搜索的数组往往是 排好序的。

--------------------

# Two Sum #

**[167. Two Sum II - Input array is sorted (Easy)][167. Two Sum II - Input array is sorted _Easy]**

**解题思路：  
使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。**

*  **如果两个指针指向元素的和 sum == targetsum==target，那么得到要求的结果；**
 *  **如果 sum > targetsum>target，移动较大的元素，使 sumsum 变小一些；**
 *  **如果 sum < targetsum<target，移动较小的元素，使 sumsum 变大一些。**

class Solution:
        def twoSum(self, numbers: List[int], target: int) -> List[int]:
            res = []
            if not numbers: return []
            left = 0
            right = len(numbers) - 1
            while (numbers[left] + numbers[right]) != target and left < right:
                if (numbers[left] + numbers[right]) > target:
                    right -= 1
                if (numbers[left] + numbers[right]) < target:
                    left += 1
            res.append(left+1)
            res.append(right+1)
            return res

--------------------

# **归并两个有序数组** #

[88. 合并两个有序数组][88.]

双指针 / 从后往前

[参考里面有动画][Link 1]

class Solution(object):
        def merge(self, nums1, m, nums2, n):
            """
            :type nums1: List[int]
            :type m: int
            :type nums2: List[int]
            :type n: int
            :rtype: void Do not return anything, modify nums1 in-place instead.
            """
            # two get pointers for nums1 and nums2
            p1 = m - 1
            p2 = n - 1
            # set pointer for nums1
            p = m + n - 1
            
            # while there are still elements to compare
            while p1 >= 0 and p2 >= 0:
                if nums1[p1] < nums2[p2]:
                    nums1[p] = nums2[p2]
                    p2 -= 1
                else:
                    nums1[p] =  nums1[p1]
                    p1 -= 1
                p -= 1
            
            # 如果p1已用完，p2还有移动的空间，则说明nums2中还有更小的几个元素，
            #这一步就是把这几个更小的元素存入nums1中。例如，nums1=[3,4,5,6,0,0,0],nums2=[1,2,2].
            nums1[:p2 + 1] = nums2[:p2 + 1]

--------------------

# 快慢指针 #

[142. 环形链表 II][142. _ II]

为什么当快慢指针第一次相遇的时候，快指针指向head？

数学思想解决：

**当未入圈时** f = s

**入圈时**：f = s +nb(n指圈数，b指一圈的步数)**即第一次相遇**

由上面f与s的关系可知f(快指针)与s(慢指针)的关系：f = 2nb，s = nb

设链表**走到链表入口节点时的步数** 为k ，**k= a +nb**

对于第一次相遇之后 s 走了**nb**步，还差a步才可以走到链表入口节点，所以这时候需要一个指针还记录**s走a步**，那a步是多少，就是链头走到链表入口的步数，所以这时候利用fast指针来记录，所以在第一次相遇之后让**fast指针指向链头head。**

class ListNode(object):
        def __init__(self, x):
            self.val = x
            self.next = None
    
    
    def detectCycle(head: ListNode) -> ListNode:
        fast = head
        slow = head
        while True:
            if not (fast.and fast.next):return
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break
        fast = head
        while fast != slow:
            fast = fast.next
            slow = slow.next
        print(fast.val)
    
    detectCycle([3,2,0,-4])

--------------------

# 数学 + 双指针 #

[888.公平的糖果][888.]

**解题思路**  
sumA - sumB 差值其实就是交换需要弥补的差距**(一开始以为是sumA，sumB以为是代表起点到指针所指，理解错误)**  
定义需要取出来的是 xA 和 xB， 那么它们差值 xA - xB = (sumA - sumB) / 2

**思路就是**：

按照从小到大的排序 A 和 B  
双指针，去遍历 A和 B， 考虑三种情况

1.  xA-xB == (sumA - sumB) / 2 找到答案，返回即可
2.  xA-xB > (sumA - sumB) / 2 , 则增大 xB
3.  xA-xB < (sumA - sumB) / 2 , 则增大 xA

class Solution:
        def fairCandySwap(self, A: List[int], B: List[int]) -> List[int]:
            A.sort()
            B.sort()
            poinerA = 0
            poinerB = 0
            sumA = sum(A)
            sumB = sum(B)
            target = (sumA - sumB) / 2
            while poinerA < len(A) and  poinerB < len(B):
                curr = A[poinerA] - B[poinerB]
                if curr > target:
                    poinerB += 1
                if curr < target:
                    poinerA += 1
                if curr == target:
                    return [A[poinerA], B[poinerB]]
    
            return []

# 哈希 #

思路及算法

记爱丽丝的糖果棒的总大小为 \\textit\{sumA\}sumA，鲍勃的糖果棒的总大小为 \\textit\{sumB\}sumB。设答案为 \\\{x,y\\\}\{x,y\}，即爱丽丝的大小为 xx 的糖果棒与鲍勃的大小为 yy 的糖果棒交换，则有如下等式：

sumA−x+y=sumB+x−y

化简得：

![20210201162057623.png][]

即对于 B 中的任意一个数 y'，只要 A中存在一个数 x' ，满足 ![20210201162207957.png][]，那么\{x′,y′\}即为一组可行解。

class Solution:
        def fairCandySwap(self, A: List[int], B: List[int]) -> List[int]:
            sera = set(A)
            suma = sum(A)
            sumb = sum(B)
            ans = None
            sumab = (suma-sumb)//2 #//2取整，2.0无法进行运算
            for i in B:
                d = i + sumab
                if d in sera:
                    ans=[d,i]
                    break
            return ans

[167. Two Sum II - Input array is sorted _Easy]: https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
[88.]: https://leetcode-cn.com/problems/merge-sorted-array/
[Link 1]: https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetcode/
[142. _ II]: https://leetcode-cn.com/problems/linked-list-cycle-ii/
[888.]: https://leetcode-cn.com/problems/fair-candy-swap/
[20210201162057623.png]: /images/20221119/18d9aa7264e8442cb6815c85b1941305.png
[20210201162207957.png]: /images/20221119/856432dfa81d46078de61078e3c2da7a.png