力扣双指针

283. 移动零所有0移动到数组的末尾同时保持非零元素的相对顺序。暴力 遍历,记录0元素数量,移动非0元素相对位置 后续补0 class Solution: def moveZeroes(self, nums: List[int]) - None: count0 for i in range(len(nums)): if nums[i]0: count 1 else: nums[i-count]nums[i] for i in range(len(nums)-count,len(nums)): nums[i]0 return nums双指针,快慢指针 慢指针记录下一个非零元素应该存放的位置 快指针遍历数组寻找非零元素 class Solution: def moveZeroes(self, nums: List[int]) - None: slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[fast],nums[slow] nums[slow] ,nums[fast] slow 111.盛水最多容器示例 1输入[1,8,6,2,5,4,8,3,7]输出49解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。双指针,一个头一个尾能装多少水取决于短板计算当前水量,判断哪个板短,移动短的保存最大水量class Solution: def maxArea(self, height: List[int]) - int: max_out0 i,j0,len(height)-1 while ij: if height[i]height[j]: max_outmax(max_out,height[i]*(j-i)) i 1 else: max_outmax(max_out,height[j]*(j-i)) j - 1 return max_out15.三数之和整数数组nums判断是否存在三元组[nums[i], nums[j], nums[k]]满足i ! j、i ! k且j ! k同时还满足nums[i] nums[j] nums[k] 0。请你返回所有和为0且不重复的三元组。排序-一个固定元素遍历数组,在这个元素后设立左右指针判断target-大于0移动右指针-小于0移动左指针,等于0记录,并跳过重复元素,之后移动双指针class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: #判断长度是否符合要求不符合返回空 if len(nums)3: return [] #创建list result [] #原数组排序,小到大 nums.sort() #双指针,i当前位置,左指针i1,右指针指向尾 for i in range(len(nums)-2): #跳过重复的i if i 0 and nums[i] nums[i-1]: continue #i0则后续都0,直接break if nums[i] 0: break #左右指针 left i1 right len(nums)-1 while left right: #三数和 target nums[i]nums[left]nums[right] #和0 移动左指针(之前已排序) if target 0: right - 1 #和0 移动右指针 elif target 0: left 1 #和0,添加结果 #同时跳过左右指针相同的元素 #保存本次结果后要移动左右指针 else: result.append([nums[i],nums[left],nums[right]]) while leftright and nums[right-1] nums[right]: right - 1 while leftright and nums[left1] nums[left]: left 1 left 1 right - 1 return result42.接雨水*示例 1输入height [0,1,0,2,1,0,1,3,2,1,2,1]输出6解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。这破玩意真反直觉左右指针,二者计算身后能存多少水,直至相遇class Solution: def trap(self, height: List[int]) - int: water 0 left,right 0, len(height)-1 max_left,max_right 0,0 #双向指针 while left right: #蓄水量取决于当前短板 #左小于右肯定计算左边 if height[left] height[right]: #左指针高度高于左边最大值,目前不能存水 #更新最大值 if height[left] max_left: max_left height[left] #能存水,计算高度差 else: water max_left - height[left] #移动左指针 left 1 else: if height[right] max_right: max_right height[right] else: water max_right - height[right] right - 1 return water