【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列：盛最多水的容器、接雨水、回文子串、三数之和

《博主简介》

小伙伴们好，我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。
?更多学习资源，可关注公-仲-hao:【阿旭算法与机器学习】，共同学习交流~
👍感谢小伙伴们点赞、关注！

《------往期经典推荐------》

一、AI应用软件开发实战专栏【链接】

项目名称	项目名称
1.【人脸识别与管理系统开发】	2.【车牌识别与自动收费管理系统开发】
3.【手势识别系统开发】	4.【人脸面部活体检测系统开发】
5.【图片风格快速迁移软件开发】	6.【人脸表表情识别系统】
7.【YOLOv8多目标识别与自动标注软件开发】	8.【基于YOLOv8深度学习的行人跌倒检测系统】
9.【基于YOLOv8深度学习的PCB板缺陷检测系统】	10.【基于YOLOv8深度学习的生活垃圾分类目标检测系统】
11.【基于YOLOv8深度学习的安全帽目标检测系统】	12.【基于YOLOv8深度学习的120种犬类检测与识别系统】
13.【基于YOLOv8深度学习的路面坑洞检测系统】	14.【基于YOLOv8深度学习的火焰烟雾检测系统】
15.【基于YOLOv8深度学习的钢材表面缺陷检测系统】	16.【基于YOLOv8深度学习的舰船目标分类检测系统】
17.【基于YOLOv8深度学习的西红柿成熟度检测系统】	18.【基于YOLOv8深度学习的血细胞检测与计数系统】
19.【基于YOLOv8深度学习的吸烟/抽烟行为检测系统】	20.【基于YOLOv8深度学习的水稻害虫检测与识别系统】
21.【基于YOLOv8深度学习的高精度车辆行人检测与计数系统】

二、机器学习实战专栏【链接】，已更新31期，欢迎关注，持续更新中~~
三、深度学习【Pytorch】专栏【链接】
四、【Stable Diffusion绘画系列】专栏【链接】

《------正文------》

1. 盛最多水的容器

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # 左右双指针
        left = 0
        right = len(height) - 1
        res = 0
        while left < right:
            if height[left] > height[right]:
                area = (right - left) * height[right]
                right -= 1
            else:
                area = (right - left) * height[left]
                left += 1
            res = max(res, area)
        return res

2.接雨水

# 左右双指针
class Solution:
    def trap(self, height: List[int]) -> int:
        # 左右双指针，一般通过while left<right循环作为终止条件
        # 某一点处的雨水与左右最大柱子的高度有关
        # left_max与right_max用于动态存储左右从左向右，及从右向左的最大高度
        # 如果left_max < right_max ,则只用考虑left点处左侧的高度即可，
        # 因为右侧的最大高度肯定比左侧高，相当于在left点处取到了左侧最大值与右侧最大值中的较小者
        n = len(height)
        left = 0
        right = n - 1
        left_max = 0
        right_max = 0
        ans = 0
        while left < right:
            if height[left] < height[right]:
                left_max = max(left_max,height[left])
                ans += left_max - height[left]
                left += 1
            else:
                right_max = max(right_max,height[right])
                ans += right_max - height[right]
                right -= 1
        return ans

#单调递减栈
class Solution:
    def trap(self, height: List[int]) -> int:
        #单调递减栈
        res = 0
        st = []
        for i in range(len(height)):
            while st and height[st[-1]] < height[i]:
                cur = st.pop()
                if not st:
                    break
                l = st[-1]
                r = i
                h = min(height[r],height[l]) - height[cur]
                res += (r-l-1) * h
            st.append(i)
        return res

3.回文子串

class Solution:
    def countSubstrings(self, s: str) -> int:
        num = 0
        n = len(s)
        for i in range(n): # 遍历回文中心点
            for j in [0,1]: # j=0,中心是一个点，j=1,中心是两个点
                l = i
                r = i + j
                while l >= 0 and r < n and s[l] == s[r]:
                    num += 1
                    l -= 1
                    r += 1
        return num

4.三数之和

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 通过排序 + 双指针实现
        nums.sort()
        res = []
        k = 0
        n = len(nums)
        for k in range(n - 2):
            if nums[k] > 0: 
                break # 1. because of j > i > k.
            if k > 0 and nums[k] == nums[k - 1]: 
                continue # 2. skip the same `nums[k]`.
            i, j = k + 1, n - 1
            while i < j: # 3. double pointer
                s = nums[k] + nums[i] + nums[j]
                if s < 0:
                    i += 1
                elif s > 0:
                    j -= 1
                else:
                    res.append([nums[k], nums[i], nums[j]])
                    i += 1
                    j -= 1
                    while i < j and nums[i] == nums[i - 1]: i += 1 # 跳过相同元素
                    while i < j and nums[j] == nums[j + 1]: j -= 1 # 跳过相同元素
        return res

关于本篇文章大家有任何建议或意见，欢迎在评论区留言交流！

觉得不错的小伙伴，感谢点赞、关注加收藏哦！

欢迎关注下方GZH：阿旭算法与机器学习，共同学习交流~