双指针问题

283. 移动零一、问题描述二、方法思路方法 双指针原地最优推荐空间 O (1)思路slow记录下一个非 0 元素该放的位置fast遍历数组找非 0 数字fast 遇到非 0和 slow 位置交换slow 右移遇到 0 直接跳过三、代码class Solution: def moveZeroes(self, nums: List[int]) - None: Do not return anything, modify nums in-place instead. # 方法一 # i 0 # s [] # for x in nums: # if x ! 0: # nums[i] x # i 1 # for j in range(i,len(nums)): # nums[j] 0 # return nums # 方法二双指针原地最优推荐空间 O (1) # slow记录下一个非 0 元素该放的位置 # fast遍历数组找非 0 数字 # fast 遇到非 0和 slow 位置交换slow 右移遇到 0 直接跳过 slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[slow],nums[fast] nums[fast],nums[slow] slow 1 return nums11. 盛最多水的容器一、问题描述二、方法思路1.两层for循环会超时2.头部和尾部两个指针分别向内收紧比较两侧高度三、代码class Solution: def maxArea(self, height: List[int]) - int: ss 0 # for i in range(len(height)): # for j in range(i): # s min(height[i],height[j])*(i-j) # ss max(s,ss) # return ss first 0 last len(height)-1 while firstlast: s min(height[last],height[first])*(last-first) if s ss: ss s if height[first]height[last]: first first1 else: last last-1 return ss15. 三数之和一、问题描述二、方法思路1.3个数中第一个数字for循环第二个数字从第一个数字后开始向后循环第三个数字从最后一个数字开始向前循环。2.若和为0添加至数列.append([nums[i],nums[j],nums[k]])去重头指针和尾指针同时移动若和小于0则头指针向后移动若和大于0则尾指针向前移动。三、代码class Solution: def threeSum(self, nums: list[int]) - list[list[int]]: n len(nums) nums.sort() s [] for i in range(n): if i0 and nums[i]nums[i-1]: continue j i1 k n-1 while jk: if nums[i]nums[j]nums[k]0: s.append([nums[i],nums[j],nums[k]]) while jk and nums[j]nums[j1]: j 1 while jk and nums[k]nums[k-1]: k - 1 j1 k-1 elif nums[i]nums[j]nums[k]0: j1 else: k-1 return (s)