本次博客我是通过Notion软件写的,转md文件可能不太美观,大家可以去我的原笔记中查看:Python蓝桥杯训练:基本数据结构 [数组],持续更新中,另外这是我创建的编程学习小组频道,想一起学习的朋友可以一起!!!
双指针法介绍:
双指针法(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
最后 return slow, 返回新数组的长度
这样我们就在原地移除了所有数值等于 val 的元素,时间复杂度为 O(n),空间复杂度为 O(1)。
class Solution:def removeElement(self, nums, val):fast, slow = 0, 0size = len(nums)while fast < size:if nums[fast] != val:nums[slow] = nums[fast]slow += 1fast += 1return slow
也可以这样写:
class Solution:def removeElement(self, nums, val):if not nums:return 0slow = 0for fast in range(len(nums)):if nums[fast] != val:nums[slow] = nums[fast]slow += 1return 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
我们只需要遍历一遍数组原地操作即可。
class Solution:def moveZeroes(self, nums):i = 0j = 0while j < len(nums):if nums[j] != 0:nums[i] = nums[j]i += 1j += 1while i < len(nums):nums[i] = 0i += 1
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 已按 升序 排列
这种思路只需要遍历一遍数组,并且是原地操作,不需要额外的空间。
class Solution:def removeDuplicates(self, nums):if not nums:return 0i = 0for j in range(1, len(nums)):if nums[j] != nums[i]:i += 1nums[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]
这种思路只需要遍历一遍数组,并且是原地操作,不需要额外的空间。
class Solution:def sortedSquares(self, nums):n = len(nums)result = [0] * ni, j = 0, n - 1k = n - 1while i <= j:if abs(nums[i]) > abs(nums[j]):result[k] = nums[i] ** 2i += 1else:result[k] = nums[j] ** 2j -= 1k -= 1return result
也可以这样去写:
class Solution:def sortedSquares(self, nums):reslut = [-1] * len(nums)k = len(nums) - 1i = 0j = len(nums) - 1while i <= j: if nums[i] ** 2 > nums[j] **2:reslut[k] = nums[i] ** 2i += 1else:reslut[k] = nums[j] ** 2j -= 1k -= 1return reslut
使用双指针法解决数组问题时需要多加思考和观察,通过不断练习来提高自己的编程能力。
这些题目都是双指针的经典题目,可以帮助你更好的理解双指针的思想。