1、移动0 （一句话概括题眼：右指针找非0元素）

• 简单

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:

输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]
示例 2:

输入: nums = [0] 输出: [0]

• 题解：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n=len(nums)
        # 初始化左右指针
        l,r=0,0
        # 让 r指针 遍历数组，直到指向非0元素，将该元素移动到前面（交换元素），左指针往前移动，右指针继续移动直到遇到非0元素，重复操作
        while r<n:
            if nums[r]!=0:
                nums[r],nums[l]=nums[l],nums[r]
                l+=1
            r+=1

2、盛最多水的容器 （底高）

• 中等

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

• 题解
• 左指针：开头，右指针：末尾
• 容积——>长方形的面积——>底*高——>（左右指针的差值） * （短板：左右指针对应的高度的较小值）

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # 初始化结果和左右指针
        res = 0
        l = 0
        r = len(height)-1
        # 只要左右指针不相遇就移动指针
        while l<r:
            # 表示底、高（高由“短板”决定）
            w = r-l
            h = min(height[l],height[r])
            res = max(res,h*w)
            # 更新左右指针
            # 左右指针在移动的时候，底在变小，因此移动方向，要让“短板”变长
            # 当右边高，就移动左指针
            if height[l] <= height[r]:
                l+=1
            else:
                r-=1
        return res

3、* 三数之和 （三指针）

• 中等

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k
且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

。

示例 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 。

注意： 答案中不可以包含重复的三元组(注意去重：三指针都要考虑去重)

• 题解
• 三指针：cur、left、right
• 1、先 sort(数组)，升序排列（特殊情况，第一个数就＞0，它后面的就不需要花时间去看了）
• 2、cur 遍历 数组，并且 left<right
• 3、三数和 的情况有三种（＞0，右指针左移）（<0左指针右移）（＝0：注意要“去重”）

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 三指针法
        # 初始化结果
        res =[]
        # 对 nums 进行排序
        nums.sort()
        # 初始化指针
        n = len(nums)
        cur = 0
        l = cur+1
        r = n-1
        
        # cur遍历nums
        for cur in range(n) :
            l = cur+1
            r = n-1
            # 排除特殊情况：
            if nums[cur]>0:
                return res
            # 对 cur 去重 nums[cur] 和nums[cur-1] 相等就跳出循环,注意：第一位不进行判断，因为它是在和最后一位进行比较，举例说明：[0,0,0,0] 返回[]
            if nums[cur] == nums[cur-1] and cur > 0:   
                continue
             # 更新l,r
            
           
            # 根据 total 的值来移动左右指针
            while l<r:
                # 计算 total
                total = nums[cur]+nums[l]+nums[r]
                # 1、如果 total>0 说明右边的值大了，要左移右指针
                if total>0: 
                    r-=1
                # 2、如果 total<0 说明左边的值小了，要右移左指针
                elif total <0: 
                    l+=1
                # 3、如果 total = 0 添加结果后，要进行内部的循环，对左指针，右指针对应的值进行去重
                else:
                    res.append([nums[cur],nums[l],nums[r]])
                    # 当左指针和下一个值相等，要移动左指针，直到左右指针相遇或者和下一个值不想等
                    while  l<r and nums[l] == nums[l+1]:
                        l+=1
                    while l<r and nums[r] == nums[r-1]:
                        r-=1 
                    l+=1
                    r-=1
      
            
        return res

4、接雨水

• 困难

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

• 题解

class Solution:
    def trap(self, height: List[int]) -> int:
        # 双指针法
        # 每个位置能接到的雨水量的和
        # 左边最大高度，右边最大高度，两者中的较小值-当前位置柱子的高度
        # 注意点：接到的雨水不能是负数，维护 MaxL,MaxR 

        # 初始化结果
        res = 0
        # 初始化左右指针
        l=0
        r=len(height)-1
        maxL = height[l]
        maxR = height[r]

        # 只要左右指针不相遇，就计算雨水量
        while l<r:
            # 因为雨水量由短板决定，因此应该先移动短板这边的方向
            if maxL < maxR:
                l+=1
                maxL = max(maxL,height[l])
                res += maxL-height[l]
            else:
                r-=1
                maxR = max(maxR,height[r])
                res += maxR-height[r]

        return res