leetcode-top100双指针专题

第一题：三数之和

题目链接

15. 三数之和 - 力扣（LeetCode）

解题思路

暴力破解

首先尝试了一个暴力破解，不出意外超时

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                for z in range(j+1,len(nums)):
                    if nums[i] + nums[j] + nums[z] == 0:
                        tmp = [nums[i],nums[j],nums[z]]
                        tmp = sorted(tmp)
                        if tmp not in result:
                            result.append(tmp)
        return result

双指针思路

算法流程

1、特判，对于数组长度n，如果数组为null或者数组长度小于3，返回[]。
2、对数组进行排序。
3、遍历排序后数组

若nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于0，直接返回结果。
对于重复元素：跳过，避免出现重复解
令左指针L=i+1，右指针R=n-1,当L<R时，执行循环：

当nums[i]+nums[L]+nums[R] == 0,执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将L,R移到下一位，寻找新的解。
若和大于0，说明nums[R]太大，R左移
若和小于0，说明nums[L]太小，L右移

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        n = len(nums)
        if n < 3:
            return result
        nums.sort()

        for i in range(n):
            if nums[i] > 0:
                return result
            if i > 0 and nums[i] == nums[i-1]:
                continue
            L = i + 1
            R = n -1
            while L < R:
                #print(i,L,R)
                tmp = nums[i]+nums[L]+nums[R]
                if tmp == 0:
                    result.append([nums[i],nums[L],nums[R]])
                    while L<R and nums[L+1] == nums[L]:
                        L += 1
                    while L<R and nums[R-1] == nums[R]:
                        R -= 1
                    L += 1
                    R -= 1
                elif tmp > 0:
                    R -= 1
                else:
                    L += 1

        return result

第二题 接雨水

题目链接

42. 接雨水 - 力扣（LeetCode）

解题思路

在马蹄集好像做过，但是还是忘记了，呜呜呜，鱼的记忆

维护两个双指针left和right，以及两个变量leftMax和rightMax，初始时left = 0,right = n -1,leftMAx = 0,rightMax = 0。指针left只会向右移动，指针right只会向左移动，在指针移动的过程中维护两个变量——leftMax和tightMax的值。

当两个指针没有相遇时，进行如下操作：

• 使用height[left]和height[right]的值更新leftMax和rightMax的值；
• 如果height[left] < height[right]，则必有leftMax < rightMax，下标left处能接的雨水加到能接的雨水总量，然后left加1（即向右移动一位）
• 如果height[left] >= height[right]，则必有leftMax >= rightMax，下标right处能接的雨水量等于rightMax - height[right]，将下标right处能接的雨水量加到能接的雨水总量，然后将right减1即向左移动一位。
  ?

解题代码

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        left,right = 0, len(height) - 1
        leftMax = rightMax = 0

        while left < right:
            leftMax = max(leftMax,height[left])
            rightMax = max(rightMax,height[right])

            if height[left] < height[right]:
                ans += leftMax - height[left]
                left += 1
            else:
                ans += rightMax - height[right]
                right -= 1
        return ans