Python蓝桥杯训练：基本数据结构 [数组]——双指针法

本次博客我是通过Notion软件写的转md文件可能不太美观大家可以去我的原笔记中查看Python蓝桥杯训练基本数据结构 [数组]持续更新中另外这是我创建的编程学习小组频道想一起学习的朋友可以一起

一、力扣上面一些关于数组的题目练习

1、双指针法

双指针法介绍
双指针法Two Pointers是一种在数组或链表等数据结构中移动两个指针来查找或遍历特定元素的算法。两个指针分别从首尾开始遍历根据题目要求不断移动指针来缩小查找范围。
双指针法常用于解决数组或链表中的滑动窗口问题、快慢指针问题、双指针问题等。其时间复杂度通常为O(n)空间复杂度为O(1)。
双指针法常见应用场景如

• 双指针法可以很好地解决链表中的快慢指针问题如找到链表中间节点或倒数第 k 个节点。
• 双指针法可以很好地解决数组中的滑动窗口问题如在数组中找到最大/小子数组、最长不重复子串等。
• 双指针法可以很好地解决回文字符串问题。

• 题目一[移除元素](https://leetcode.cn/problems/remove-element/)

不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例1

输入nums = [3,2,2,3], val = 3
输出2, nums = [2,2]
解释函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如函数返回的新长度为 2 而 nums = [2,2,3,3] 或 nums = [2,2,0,0]也会被视作正确答案。

示例2

输入nums = [0,1,2,2,3,0,4,2], val = 2
输出5, nums = [0,1,4,0,3]
解释函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

---

首先定义两个快慢指针一个指针 fast 指向当前遍历到的位置另一个指针 slow 指向新数组的尾部初始化 fast 和 slow 指针都为0意思是开始都指向索引为0的位置定义一个变量size为nums的长度然后使用while循环进行判断当 fast 指针没有遍历完整个数组时比对当前的nums[fast] 和 val

• 如果不等于把当前的nums[fast] 移动到nums[slow], 并且把 slow 向后移动一位
• 如果相等则不做任何操作
• fast 指针每次遍历结束时指针向后移动一位

最后 return slow, 返回新数组的长度
这样我们就在原地移除了所有数值等于 val 的元素时间复杂度为 O(n)空间复杂度为 O(1)。

---

class Solution:
    def removeElement(self, nums, val):
        fast, slow = 0, 0
        size = len(nums)
        while fast < size:
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

也可以这样写

class Solution:
    def removeElement(self, nums, val):
        if not nums:
            return 0
        slow = 0
        for fast in range(len(nums)):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
        return slow

B站上面卡尔老师对于这道题的思路讲得很不错在这里推荐大家去看看他的教学视频

https://www.bilibili.com/video/BV12A4y1Z7LP/?spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=eae0406d86828f39f6ac3a3b0e8a2a34

---

• 题目二[移动零](https://leetcode.cn/problems/move-zeroes/)

请注意 必须在不复制数组的情况下原地对数组进行操作。

示例1

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例2

输入: nums = [0]
输出: [0]

提示

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

---

1. 创建两个指针 i 和 ji 指向当前遍历到的元素j 指向下一个非零元素
2. 从数组的第一个元素开始遍历
3. 当 i 指向的元素为0时将j指向的元素复制到i指向的元素位置i和j都后移一位。
4. 如果i指向的元素不是0i和j都后移一位
5. 遍历完整个数组后所有的0都会被移到数组的末尾

我们只需要遍历一遍数组原地操作即可。

---

class Solution:
    def moveZeroes(self, nums):
        i = 0
        j = 0
        while j < len(nums):
            if nums[j] != 0:
                nums[i] = nums[j]
                i += 1
            j += 1
        while i < len(nums):
            nums[i] = 0
            i += 1

---

1. 创建一个变量 zero用来记录0的位置
2. 从数组的第一个元素开始遍历
3. 如果当前遍历到的元素不是0就将它与zero位置的元素交换并将zero位置后移一位
4. 遍历完整个数组后所有的0都会被移到数组的末尾

---

class Solution:
    def moveZeroes(self, nums):
        zero = 0  # 记录“0”的位置
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[i], nums[zero] = nums[zero], nums[i]
                zero += 1

---

• 题目三[删除有序数组中的重复项](https://leetcode.cn/problems/remove-duplicates-from-sorted-array/)

由于在某些语言中不能改变数组的长度所以必须将结果放在数组nums的第一部分。更规范地说如果在删除重复项之后有 k 个元素那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例1

输入nums = [1,1,2]
输出2, nums = [1,2,_]
解释函数应该返回新的长度 2 并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例2

输入nums = [0,0,1,1,1,2,2,3,3,4]
输出5, nums = [0,1,2,3,4]
解释函数应该返回新的长度 5  并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 升序 排列

---

1. 创建两个指针 i 和 ji 指向当前遍历到的元素j 指向下一个元素
2. 从数组的第二个元素开始遍历
3. 当 j 指向的元素和 i 指向的元素不同时就将 j 指向的元素赋值给 i+1的位置i和j都后移一位
4. 如果j指向的元素和 i 指向的元素相同j 后移一位
5. 遍历完整个数组后所有重复项都会被删除。

这种思路只需要遍历一遍数组并且是原地操作不需要额外的空间。

---

class Solution:
    def removeDuplicates(self, nums):
        if not nums:
            return 0
        i = 0
        for j in range(1, len(nums)):
            if nums[j] != nums[i]:
                i += 1
                nums[i] = nums[j]
        return i + 1

---

• 题目四[有序数组的平方](https://leetcode.cn/problems/squares-of-a-sorted-array/)

示例1

输入nums = [-4,-1,0,3,10]
输出[0,1,9,16,100]
解释平方后数组变为 [16,1,0,9,100]
排序后数组变为 [0,1,9,16,100]

示例2

输入nums = [-7,-3,2,3,11]
输出[4,9,9,49,121]

提示

输入nums = [-7,-3,2,3,11]
输出[4,9,9,49,121]

---

1. 创建一个结果数组result并初始化为0。
2. 创建三个指针i,j,k。 i 指向数组最左边,j指向数组最右边,k指向结果数组最右边
3. 使用while循环当i小于等于j时循环比较i指向的数和j指向的数的绝对值的大小。
4. 如果i指向的数的绝对值大于j指向的数的绝对值就将i指向的数的平方放入result中并将i指针后移一位。否则将j指向的数的平方放入result中并将j指针前移一位。
5. 最后返回result

这种思路只需要遍历一遍数组并且是原地操作不需要额外的空间。

---

class Solution:
    def sortedSquares(self, nums):
        n = len(nums)
        result = [0] * n
        i, j = 0, n - 1
        k = n - 1
        while i <= j:
            if abs(nums[i]) > abs(nums[j]):
                result[k] = nums[i] ** 2
                i += 1
            else:
                result[k] = nums[j] ** 2
                j -= 1
            k -= 1
        return result

也可以这样去写

class Solution:
    def sortedSquares(self, nums):
        reslut = [-1] * len(nums)
        k = len(nums) - 1
        i = 0
        j = len(nums) - 1
        while i <= j: 
            if nums[i] ** 2 > nums[j] **2:
                reslut[k] = nums[i] ** 2
                i += 1
            else:
                reslut[k] = nums[j] ** 2
                j -= 1
            k -= 1
        return reslut

---

1. 了解题目要求判断是否适用双指针法。
2. 确定指针的初始位置和移动规则。
3. 注意每次移动指针时的边界条件。
4. 注意在循环中进行的比较和赋值操作。
5. 注意结果数组的初始化和最终返回结果。
6. 注意空间复杂度尽量使用原地算法。
7. 多加思考多加练习。

使用双指针法解决数组问题时需要多加思考和观察通过不断练习来提高自己的编程能力。

---

• 第26题删除排序数组中的重复项
• 第27题移除元素
• 第75题颜色分类
• 第88题合并两个有序数组
• 第67题两数之和 II - 输入有序数组
• 第9题长度最小的子数组
• 第53题会议室 II
• 第45题反转字符串中的元音字母
• 第67题字符串的排列
• 第81题最短无序连续子数组
• 第77题有序数组的平方

这些题目都是双指针的经典题目可以帮助你更好的理解双指针的思想。