【经典LeetCode算法题目专栏分类】【第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

# 左右双指针
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

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

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