leetcode-top100双指针专题

发布时间:2024年01月24日

第一题:三数之和

题目链接

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

文章来源:https://blog.csdn.net/weixin_53908842/article/details/135819102
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。