LeetCode | 双指针
981 字
5 分钟
LeetCode | 双指针
分类：双指针 / 总结
讲解
双指针题目的核心是：用两个指针描述当前正在处理的位置或范围，然后根据规则移动指针。
移动零 的 left 和 right 一开始都在数组最左侧。right 不断向右扫描数组；当 right 看到非零数时，就把它交换到 left 指向的位置，然后 left 向右移动。最后数组前面是所有非零数，后面是所有 0。
盛最多水的容器 的 left 一开始在最左侧，right 一开始在最右侧。两个指针夹住一个容器，计算当前面积后，移动较短的那一边；如果右边更短就移动 right，如果左边更短就移动 left。最后返回最大面积。
三数之和 先排序并固定第一个数 nums[i]，然后让 left 从 i + 1 开始，right 从数组最右侧开始，在右侧区间里找另外两个数。如果三数之和偏小，就移动 left；如果三数之和偏大，就移动 right；如果等于 0，就记录答案并同时移动两个指针。最后返回所有不重复的三元组。
接雨水 的 left 一开始在最左侧，right 一开始在最右侧，同时维护 left_max 和 right_max。如果左边高度更低，就结算 left 位置能接的水，然后移动 left；否则结算 right 位置能接的水，然后移动 right。最后返回总水量。
最长回文子串 的 left 和 right 一开始都指向同一个中心位置（偶数长度回文则指向相邻两个字符）。只要 s[left] 和 s[right] 相等，就不断向两侧扩展，记录扩展出的回文串；每个中心都试过后，返回最长的回文子串。
双指针题目重要是：两个指针分别代表什么，什么时候移动左边，什么时候移动右边。
代码
移动零
from typing import List
class Solution: def moveZeroes(self, nums: List[int]) -> None: n = len(nums) left = right = 0 while right < n: if nums[right]: nums[left], nums[right] = nums[right], nums[left] left += 1 right += 1盛最多水的容器
from typing import List
class Solution: def maxArea(self, height: List[int]) -> int: left = 0 right = len(height) - 1
ans = 0 while left < right: if height[right] < height[left]: h = height[right] area = (right - left) * h if area > ans: ans = area right -= 1 while left < right and height[right] < h: right -= 1 else: h = height[left] area = (right - left) * h if area > ans: ans = area left += 1 while left < right and height[left] < h: left += 1
return ans三数之和（双指针）
from typing import List
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() ans = [] n = len(nums)
for i in range(n - 2): if i > 0 and nums[i] == nums[i - 1]: continue if nums[i] > 0: break
left = i + 1 right = n - 1 while left < right: total = nums[i] + nums[left] + nums[right] if total < 0: left += 1 elif total > 0: right -= 1 else: ans.append([nums[i], nums[left], nums[right]]) left += 1 right -= 1 while left < right and nums[left] == nums[left - 1]: left += 1 while left < right and nums[right] == nums[right + 1]: right -= 1
return ans接雨水
from typing import List
class Solution: def trap(self, height: List[int]) -> int: ans = 0 left = 0 right = len(height) - 1 left_max = 0 right_max = 0
while left < right: left_max = max(left_max, height[left]) right_max = max(right_max, height[right])
if height[left] < height[right]: ans += left_max - height[left] left += 1 else: ans += right_max - height[right] right -= 1
return ans最长回文子串（中心扩展）
class Solution: def longestPalindrome(self, s: str) -> str: def expand(left: int, right: int) -> str: while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return s[left + 1:right]
ans = "" for i in range(len(s)): odd = expand(i, i) even = expand(i, i + 1) ans = max(ans, odd, even, key=len) return ans参考资料
- 移动零
- 盛最多水的容器
- 三数之和
- 接雨水
- 最长回文子串
- LeetCode 移动零：https://leetcode.com/problems/move-zeroes/
- LeetCode 盛最多水的容器：https://leetcode.com/problems/container-with-most-water/
- LeetCode 三数之和：https://leetcode.com/problems/3sum/
- LeetCode 接雨水：https://leetcode.com/problems/trapping-rain-water/
- LeetCode 最长回文子串：https://leetcode.com/problems/longest-palindromic-substring/
- 力扣移动零题解：https://leetcode.cn/problems/move-zeroes/solutions/489622/yi-dong-ling-by-leetcode-solution/
- 力扣盛最多水的容器题解：https://leetcode.cn/problems/container-with-most-water/solutions/11491/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
- 力扣三数之和题解：https://leetcode.cn/problems/3sum/solutions/284681/san-shu-zhi-he-by-leetcode-solution/
- 力扣接雨水题解：https://leetcode.cn/problems/trapping-rain-water/solutions/692342/jie-yu-shui-by-leetcode-solution-tuvc/
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
相关文章智能推荐
1
LeetCode | 移动零
LeetCodeLeetCode 移动零题解：使用双指针原地移动零，同时保持非零元素相对顺序。
2
LeetCode | 接雨水
LeetCodeLeetCode 接雨水题解：理解每个位置的左右挡板，用双指针在线性时间内计算总积水量。
3
LeetCode | 哈希表
LeetCode整理 LeetCode 哈希表题目的核心思路：先建表，再查表。
4
LeetCode | 最长回文子串
LeetCodeLeetCode 最长回文子串题解：中心扩展法枚举每个奇偶中心向两侧扩展，时间复杂度 O(n²)，空间复杂度 O(1)。
5
LeetCode | 盛最多水的容器
LeetCodeLeetCode 盛最多水的容器题解：使用双指针从两端向中间移动，计算能够装下的最大水量。
随机文章随机推荐
评论区
--
总访问量
--
访客数
音乐
暂未播放
0:000:00
文章
66
分类
16
标签
93
总字数
477,284
运行时长
0 天
最后活动
0 天前
