双指针专题

本文最后更新于：2023年3月5日 下午

简单介绍下双指针

双指针正如其名，如果一个指针不够用，那就用两个指针来解决问题！当然指针只是个叫法，并不是一定要用指针，普通的变量作索引，能够辅助解决问题的都可以。
双指针和滑动窗口其实也能扯上关系，毕竟滑窗要用到left和right来确定窗口的左右边界嘛，那么这里的left和right就能看成是双指针啦~

双指针相关题目

977. 有序数组的平方

题目链接：977
自己最开始想到的思路就是，由于nums已经按照非递减顺序顺序排序了，那么在平方后，我们可以以负数和非负数为分界线，分出两个数组，左边的负数数组从右往左看是递增的，右边的非负数数组从左往右看是递增的，也就是说我们的两个指针可以设置在分界点这里，一个往左走一个往右走，每次比较两数大小，小的就放进去结果ans中，然后更新指针，直至把数全部塞进ans中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        positive = negative = 0
        nums_pow = [nums[0] * nums[0]]
        ans = []
        for n in range(1, len(nums)):  # 求出平方数组
            if nums[n - 1] < 0 and nums[n] >= 0:  # 找到左右两个递增数组的开头
                negative = n - 1
                positive = n
            nums_pow.append(nums[n] * nums[n])
        if positive == negative:  # 两者都是0，说明nums数组只含有一个单调数组
            if nums[0] >= 0:
                return nums_pow
            else:
                nums_pow.reverse()
                return nums_pow
        while positive < len(nums) and negative >= 0:
            if nums_pow[positive] > nums_pow[negative]:
                ans.append(nums_pow[negative])
                negative -= 1
            else:  # nums_pow[positive] <= nums_pow[negative]
                ans.append(nums_pow[positive])
                positive += 1
        while negative >= 0:
            ans.append(nums_pow[negative])
            negative -= 1
        while positive < len(nums):
            ans.append(nums_pow[positive])
            positive += 1
        return ans

上面是初版代码，看完别人的代码后再看自己的，就发现肉眼可见的看上去就很复杂，“复杂”主要体现在对特殊情况进行了处理，循环完后还要多写两个判断来处理剩下的数，以及为什么要先求一个挺没有意义的平方数组(逃)。
当然，更优的思路是从将双指针设置在nums数组的左右边界，即0和nums.Length - 1，将ans初始化为跟nums长度一致，每次比较数，把大数放到ans末尾即可（即逆序放入数组中）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int[] SortedSquares(int[] nums) {
        int n = nums.Length;
        int[] ans = new int[n];
        int i = 0, j = n - 1, pos = n - 1;
        while (i <= j)
		{
            if (nums[i] * nums[i] > nums[j] * nums[j])
			{
                ans[pos] = nums[i] * nums[i];
                i += 1;
            }
            else
			{
                ans[pos] = nums[j] * nums[j];
                j -= 1;
            }
            pos -= 1;
        }
        return ans;
    }
}

283. 移动零

题目链接：283
看完题目，简单总结一下就是：要把所有非0数放在数组的左边（也就是所有0的左边），所有0放在数组的右边（也就是所有非0数的右边），且要保持非0元素的相对顺序。
利用双指针，从头扫到尾，保证left的左边是排序好的非0元素，right则用于寻找剩下的非0元素，并将它们放到左边。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        left = right = 0
        while right < n:
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
            right += 1

167. 两数之和 II - 输入有序数组

题目链接：167
这题的双指针思路算是很容易就能想到的了，而且题目也说了数组已按非递减顺序排列且一定存在解，那么就直接设置left和right为numbers数组的左右边界，如果左右相加大了，就让右指针向左移动，反之如果小了，就让左指针向右移动。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        left = 0
        right = n - 1
        while left < right:
            if numbers[left] + numbers[right] == target:
                return [left + 1, right + 1]
            elif numbers[left] + numbers[right] < target:
                left += 1
            else:  # numbers[left] + numbers[right] > target
                right -= 1

557. 反转字符串中的单词 III

题目链接：557
其实这题我并没有用双指针来写，因为Python的方法真是太好用了(逃)。
不过既然都是双指针专题了，那就大概讲讲思路，不敲代码了(因为真的很简单)。首先利用for循环遍历字符串，for循环中的索引同时也担当指针，每次循环记录当前索引位置，并将索引定位到当前单词后面空格的位置，双指针的位置就确定完毕了。

876. 链表的中间结点

题目链接：876
这道题就触及到我的知识盲区了，后面看了看，搜嘎，原来还有个“快慢指针”的分支啊~
如同它的名字一般，我们设置两个指针，一个走得快，走在前面，一个走得慢，走在后面。对于这道题，我们需要找到在链表中间的结点，那么我们是否可以让快指针走完链表的时候，慢指针刚好到中间结点呢？
那肯定可以啦，中间结点不是除以2嘛，那就让快指针的速度是慢指针的两倍，也就是慢指针每次走一步，快指针每次走两步即可。

1
2
3
4
5
6
7
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
        return slow

19. 删除链表的倒数第 N 个结点

题目链接：19
那么这题就和上面那道链表题一样了，其思想都是快慢指针，我们所需要思考的就是快指针与慢指针的相对距离。
题目说要删除的是倒数第n个结点，那么我们就想要快指针遍历完的时候，慢指针要在那个应该删除的结点的前面那个结点上面（为什么呢？这就涉及到链表删除结点这个操作的知识了，可以看链表相关知识）。
那么我们就先让快指针先走n个结点，然后快慢指针同时走，就能够保持两个指针的距离相对不变了。
诶，停一下，细心的朋友已经发现了这么走的话最后慢指针应该是在应该删除的结点上面，而不是它前面那个结点，那怎么办呢？那就设置一个哨兵结点ListNode(0, head)，这也是链表常用技巧。
到这里思路就完整了，接下来写出代码即可。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        fast = head
        slow = ListNode(0, head)
        for _ in range(n):
            fast = fast.next
        while fast is not None:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return head

题外话

我趣，一天写完是真累啊，就应该写一题马上更新，堆在一起简直要命(倒)
以后也会保持更新的吧(心虚

这里有一只爱丽丝

希望本文章能够帮到您~

Solution
#C# #Python #Leetcode #双指针
双指针专题
https://map1e-g.github.io/2023/03/05/algorithm-two-pointers/
作者
MaP1e-G
发布于
2023年3月5日
许可协议