力扣（python3自用）

m0_68478087

358人浏览 · 2026-03-30 16:37:27

m0_68478087 · 2026-03-30 16:37:27 发布

问了ai之后，明白自己应该先梳理思路，在说一些细节问题。先把思路理清，把框架搭建起来。最好可以先写注释，30min之后，这道题不管什么地步，都要暂停去看答案。

11.盛最多水的容器

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

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

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

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

思路：直觉是从底部最长的开始寻找，两边指针，谁小移动谁，不断更新ans

class Solution:
    def maxArea(self, height: List[int]) -> int:
        res = 0
        i = 0
        j = len(height) - 1
        while i < j:
            h = min(height[i],height[j])
            res = max(res,h*(j-i))
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return res

15.三数之和

给你一个整数数组 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] 。
注意，输出的顺序和三元组的顺序并不重要。

思路：人类直觉，首先进行排序，遍历数组，然后左右指针。当sum < 0，那就是右移左指针，当sum > 0，那就是左移右指针。当 sum = 0 那就需要把当前 i l r代表的数值维护到结果中，移动双指针，并且跳过l r重复的数值。后续 i 有重复的，需要跳过

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums = sorted(nums)
        res = []
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            if nums[i] > 0:
                break
            l = i + 1
            r = len(nums) - 1
            
            while l < r:
                if nums[i] + nums[l] + nums[r] == 0:
                    res.append([nums[i],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
                elif nums[i] + nums[l] + nums[r] < 0:
                    l += 1
                else:
                    r -= 1
            
        return res

3.无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

思路：需要 dict 维护当前窗口字符对应的索引。遍历字符串，当出现重复字符的时候，需要判断，该字符的索引和 l 的关系，如果索引 < l，则无影响，需要更新字符对应的索引；如果索引 >= l，则需要更新 l 的位置。遍历过程需要不断维护最长长度。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 字符串遍历，找到重复的就从重复出现的第一个位置再开始找
        # 维护一个字典，将字符映射到索引
        # 边遍历边维护，当遍历字符是前面出现过的，更新左边界，更新当前字符的字典映射。可是左边界更新之后，中间的映射怎么办？
        dct = {}
        l = 0
        ans = 0
        for i in range(len(s)):
            if s[i] in dct:  # 出现重复
                if dct[s[i]] >= l:
                    l = dct[s[i]] + 1
            dct[s[i]] = i
            ans = max(ans,i - l + 1)
        return ans

560.和为K的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

思路：感觉很多时候，计算机中是看右侧的那种感觉。这个是用前缀和pre_sum维护每个位置前面累积和。然后pre_sum之间各个元素的差值，如果是 k 那就是找到了和为k的子数组。这个地方可以用两数之和的思想。 a + b = k 这个题就是 a + (-b) = k。需要注意的是前缀和需要单独维护pre_sum[0] = 0,然后pre_sum[1]就是第一个元素，pre_sum[2]是第1个元素+第2个元素。因为要考虑到从1 到 i 元素和为 k 。

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # 前缀和 pre_sum[i] 表示i位置前缀和
        # 前缀和pre_sum 中元素两数之差为k 也就是a+(-b) =k 参考两数之和
        # 构造mp字典，pre_sum元素是key ,value表示当前出现的次数，res维护最后结果
        pre_sum = [0] * (len(nums) + 1)
        # pre_sum[0] = nums[0]
        res = 0
        pre_sum[0] = 0
        for i in range(0,len(nums)):
            
            pre_sum[i + 1] = pre_sum[i] + nums[i]
        mp =  defaultdict(int)
        for i in range(len(pre_sum)):
            if (-k + pre_sum[i]) in mp:
                res += mp[(-k + pre_sum[i])]
            
            mp[pre_sum[i]] += 1
        print(pre_sum)
        return res

239.滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

思路：这种题就是人类直觉没有办法模拟的感觉。我觉得可能我之后还是会忘记。现在的思路是维护一个双端队列，表示候选最大值的索引。其中对头为当前窗口的最大值的索引。

遍历数组，如果当前值 > 队尾，那就需要把队尾踢出去；如果 < 队尾，那就当作候选最大值，加入队尾；每次遍历需要看对头的索引和 l 边界的问题，如果已经不在窗口中，需要把对头踢出去。

from collections import deque
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 需要首先找到第一个窗口中的最大值
        # 移动窗口，先判断右面的新进来和当前最大值关系，需不需要更新最大值；以及最大值是否已经出窗口了
        #需要维护最大值对应的索引mp[max_num] >= l and >nums[right] ans = max_num
        # mp[max_num] >=l and < nums[right] ans = nums[right]
        # mp[max_num] <l  重新维护最大值。怎么重新维护，也就是一开始怎么维护窗口中的最大值？？用栈？？
        # 用双端队列维护一些候选最大值的索引
        # 队头表示当前窗口的最大值，后面的是候选最大值。
        # 窗口移动，需要判断：
        # 右侧新值 >= 队尾值 ，队尾出队，循环
        # 右侧新值 < 队尾值，进队列当候选最大值
        # 移动窗口的左侧边界大于对头索引的话，对头出队
        q = deque()
        r = 0
        ans = -inf
        res = []
        for r in range(len(nums)):
            l = r - k + 1
            if q and q[0] < l:
                q.popleft()
            while q and nums[r] >= nums[q[-1]]:
                q.pop()
            
            q.append(r)
            # ans = max(ans,nums[q[0]])
            if l >= 0:
                res.append(nums[q[0]])
        return res

76.最小覆盖子串

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。

测试用例保证答案唯一。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

思路：这个也是需要先看右侧的指针，也就是右侧一直找，直到s子串能覆盖t子串了，那就开始缩小左侧指针，不断维护左指针和右指针。更新s_cnt。

class Solution:
    def check(self,s_cnt,t_cnt):
        for key in t_cnt:
            if s_cnt[key] < t_cnt[key]:
                return 0
        return 1
    def minWindow(self, s: str, t: str) -> str:
        # 1、准备s_cnt 和 t_cnt分别统计字符串中字符出现的数量
        # 右指针是探索者，一直右移直到s_cnt覆盖了t_cnt
        # 左指针是清理者，当覆盖了之后，左指针右移，s_cnt[s[l]]-- ,l++ 直到不能覆盖为止 更新l 和r 直到最后把l r 之间的字符串打印
        s_cnt = defaultdict(int)
        t_cnt = defaultdict(int)
        for i in range(len(t)):
            t_cnt[t[i]] += 1
        print(t_cnt)
        l = 0
        r = 0
        ans = inf
        r_min = inf
        l_min = inf
        for r in range(len(s)):
            s_cnt[s[r]] += 1
            while self.check(s_cnt,t_cnt):
                if ans > (r - l + 1):
                    r_min = r
                    l_min = l
                    ans = r - l + 1
                s_cnt[s[l]] -= 1
                l += 1
        print(s_cnt)
        print(r_min,l_min)
        if ans == inf:
            return ""
        else: 
            return s[l_min:r_min + 1]