LeetCode算法刷题——双指针

双指针算法的定义：

双指针算法是一种在数组、链表或其他线性数据结构上使用两个“指针”（通常是索引或引用）协同遍历，以高效解决问题的算法技巧。这里的“指针”不一定是指 C/C++ 中的内存指针，更多是指数组下标或迭代器。

通过维护两个指针（如左指针 left 和右指针 right），根据问题的性质动态地移动它们，从而避免使用嵌套循环，将时间复杂度从 O（n²）优化到O（n）。

常见类型：

普通双指针：一般情况下两个指针往同一个方向移动。

对撞双指针：两个指针面对面移动。

快慢双指针：一快一慢同向移动。

LeetCode练习题—[141]环形链表

本题为简单题，目的是为了考察对于双指针算法的运用，本题运用的方法为快慢双指针。

注：以下解法仅代表个人观点，并非唯一解法，仅供记录与参考！

题目如下所示：

代码解析（python）：

# # @lc app=leetcode.cn id=141 lang=python3 # # [141] 环形链表 # # @lc code=start # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: # 如果链表为空或只有一个节点，直接返回False if head is None: return False # 使用快慢指针法，初始都指向头节点 slow = head fast = head # 当快指针和快指针的下一个节点都不为空时继续循环 while fast is not None and fast.next is not None: # 慢指针每次前进一步 slow = slow.next # 快指针每次前进两步 fast = fast.next.next # 如果快慢指针相遇，说明存在环 if slow == fast: return True # 如果循环结束仍未相遇，说明没有环 return False

LeetCode练习题—[881]救生艇

本题为中等题，目的是为了考察对于双指针算法的运用，本题运用的方法为对撞双指针。

注：以下解法仅代表个人观点，并非唯一解法，仅供记录与参考！

题目如下所示：

代码解析（python）：

# # @lc app=leetcode.cn id=881 lang=python3 # # [881] 救生艇 # # @lc code=start class Solution: def numRescueBoats(self, people: List[int], limit: int) -> int: # 如果人员列表为空或为None，直接返回0 if people is None or len(people) == 0: return 0 # 将人员按体重升序排序 people.sort() # 初始化双指针：i指向最轻的人，j指向最重的人 i = 0 j = len(people) - 1 res = 0 while i <= j: # 当还有人员需要上船时循环 if people[i] + people[j] <= limit: # 如果最轻的人和最重的人可以同乘一艘船 i += 1 # 最轻的人上船 j -= 1 # 最重的人总是上船 res += 1 # 使用了一艘船 return res