leetcode-hot100-双指针

剪���，减少不必要的计算

283. 移动零

示例 1:

输入: nums = [0,1,0,3,12]

输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]

输出: [0]

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

第一印象：使用一个辅助数组，同时以0进行初始化，遍历nums，依次将非零元素复制到辅助数据中；最后将辅助数组赋值给原数组。

但是，题目要求不复制数组原地修改数据进行操作。

想办法直接修改原数组，我们使用两个指针，p1、p2分别表示新数组中可以插入元素的下标，当前数组中遍历的元素；遍历数组时，找到非零元素同时将元素保存到p1下–通过交换元素实现，如果是非零元素，则继续遍历。

p1 = 0for p2 in range(len(nums)):if nums[p2] != 0:nums[p1], nums[p2] = nums[p2], nums[p1]p1 += 1

class Solution(object):def moveZeroes(self, nums):""":type nums: List[int]:rtype: None Do not return anything, modify nums in-place instead."""if not nums:return 0j = 0for i in range(len(nums)):if nums[i]:nums[j], nums[i] = nums[i], nums[j]j += 1

11. 盛最多水的容器

输入：[1,8,6,2,5,4,8,3,7]

**输出：49

解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

朴素思路：查找所有可以盛水的容器，计算容量，找到最多水的容器。使用双层循环。

容器的容量 = 两边的短板高度 x 容器长度，

result = 0for i in range(N):for j in range(i+1, N):temp = min(nums[i], nums[j]) * (j - i)result = max(result, temp)return result

这种思路中，计算所有可能的容器，因此复杂度过高。所以，优化思路是减少循环次数，去掉不必要的解。同样采用双指针(ps：双循环也算一种双指针)，left，right初始化为0、N-1，数组的起始和终止位置–容器长度最大。此时计算一下容量，之后移动left和right中的小值。

left, right = 0, N - 1result = 0while left  
class Solution:    def maxArea(self, height: List[int]) -> int:        i, j, res = 0, len(height) - 1, 0        while i  
15.三数之和
 
示例 1：
 
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
 
示例 2：
 
输入：nums = [0,1,1]
输出：[]
**解释：唯一可能的三元组和不为 0 。
 
示例 3：
 
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
 
朴素思路：3层循环/三指针，查找所有3元组，判断和是否等于0，通过限制i、j、k的取值范围保证可以保证不重复取值，但是无法保证没有重复的三元组，所以一种思路就是找到所有解最后去重。
缺点是时间复杂度过高。
 
另一种思路，类似于两数之和, 外围一层循环，内层循环查找两数之和等于0-nums[i]的数组，如果找到，加入到结果中，同时进行去重操作，将数组中前后等于当前元素的下标都跳过(所以，最先一步是排序，保证相同元素都连续出现，方便后续进行去重操作)，这里去重之后，就不用最后对结果去重。
 
class Solution:    def threeSum(self, nums: List[int]) -> List[List[int]]:        n = len(nums)        if n  0: # 剪枝：第一个元素>0,则一定不会出现对应的3元组；排序后                return res            if i > 0 and nums[i] == nums[i-1]:#去重                continue            L = i + 1            R = n - 1            while L 0:                    R = R - 1                else:                    L = L + 1        return res
 
42. 接雨水
 
给定 n 个非负整数表示每个宽度为 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 个单位的雨水（蓝色部分表示雨水）。
 
我们需要做两点：1.判断当前位置能否可以接雨水？2. 如果可以，雨水容量是多少
能否接：需要判断当前点是否为一个凹点，即当前点的左边、右边是否有高于当前位置的元素，如果有，其容量 = min(max_left, max_right) - height[i]
 
class Solution:    def trap(self, height: List[int]) -> int:        ans = 0         ml = [0] * len(height)        mr = [0] * len(height)                for i in range(1, len(height)):            ml[i] = max(ml[i - 1], height[i - 1])        for i in range(len(height) - 2, -1, -1):            mr[i] = max(mr[i + 1], height[i + 1])        for i in range(1, len(height) - 1):            tmp = min(ml[i], mr[i])            if height[i]  
class Solution {public:    int trap(vector& height) {        int n = height.size();        int left = 0, right = n - 1;        int leftMax = height[left], rightMax = height[right];        ++left, --right;        int ans = 0;        while(left             leftMax = max(leftMax, height[left]);            rightMax = max(rightMax, height[right]);            if(leftMax