2025-03-31#

56. 合并区间 - 力扣（LeetCode）

这道题挺简单的，注意到区间的连续性，可以选择先把所有区间根据 start 进行排序，以减少时间复杂度。另外需要考虑到排序后前后两个区间的相对关系，共有如 [1,4] 和 [2, 6]、[1, 4] 和 [2, 3]、[1, 4] 和 [5, 6] 这三种情况。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals = sorted(intervals, key=lambda x: x[0])
        start = intervals[0][0]
        end = intervals[0][1]
        ans = []
        for interval in intervals:
            if interval[0] <= end:
                if interval[1] >= end:
                    end = interval[1]
            else:
                ans.append([start, end])
                start = interval[0]
                end = interval[1]
        ans.append([start, end])
        return ans

2025-03-30#

239. 滑动窗口最大值 - 力扣（LeetCode）

很简单的滑动窗口，不必多说；唯一需要注意的点是 python 中 heapq 默认是小根堆。

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)
        ans = [-q[0][0]]
        for i in range(k, len(nums)):
            heapq.heappush(q, (-nums[i], i))
            while q[0][1] <= i - k:
                heapq.heappop(q)
            ans.append(-q[0][0])
        return ans

2025-03-27#

560. 和为 K 的子数组 - 力扣（LeetCode）

这道题用前缀和可以做，但是想了想似乎加上哈希优化一下，时间复杂度会降到 $O(n)$ 去，所以就没有必要保存前缀和数组了；另外边界情况也要注意到。

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        pre_dict = {}
        pre = 0
        cnt = 0
        for i in range(len(nums)):
            pre += nums[i]
            cnt += pre_dict.get(pre - k, 0)
            if pre in pre_dict.keys():
                pre_dict[pre] += 1
            else:
                pre_dict[pre] = 1
            if pre == k:
                cnt += 1
        return cnt

2025-03-26#

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

很典的滑动窗口，导致我的做法和官方题解几乎一样……

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        len_s, len_p = len(s), len(p)

        ans = []
        if len_s >= len_p:
            s_count = [0] * 26
            p_count = [0] * 26
            for i in range(len_p):
                s_count[ord(s[i]) - 97] += 1
                p_count[ord(p[i]) - 97] += 1
    
            if s_count == p_count:
                ans.append(0)
    
            for i in range(len_s - len_p):
                s_count[ord(s[i]) - 97] -= 1
                s_count[ord(s[i + len_p]) - 97] += 1
                
                if s_count == p_count:
                    ans.append(i + 1)

        return ans    

2025-03-25#

3. 无重复字符的最长子串 - 力扣（LeetCode）

从无重复字符，可以想到用 set 的数据结构维护一个子串所包含的所有字符，并用于查询新字符是否已经存在；然后用双指针记录当前子串左右边界，并且注意到每次左指针向右移动后，右指针一定是“不减”的。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l: int = 0
        r: int = 1
        max_l = 0
        chars = set()
        for l in range(len(s)):
            if not l == 0:
                chars.discard(s[l - 1])
            chars.add(s[l])
            r = max(l + 1, r)
            while r < len(s):
                if not s[r] in chars:
                    chars.add(s[r])
                    r += 1
                else:
                    break
            max_l = max(max_l, r - l)
        return max_l

2025-03-24#

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

主要思路：先排序，然后双指针移动

class Solution:
    def check(self, i: int, j: int, k: int, nums: List[int]):
        return nums[i] + nums[j] + nums[k] == 0
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        ans = []
        for i in range(len(nums) - 2):
            if i == 0 or nums[i] != nums[i - 1]:
                k = len(nums) - 1
                for j in range(i + 1, len(nums)):
                    if j == i + 1 or nums[j] != nums[j - 1]:
                       while k > j and nums[i] + nums[j] + nums[k] > 0:
                           k -= 1
                       if k == j:
                           continue
                       if self.check(i, j, k, nums):
                          ans.append([nums[i], nums[j], nums[k]])
        return ans

42. 接雨水 - 力扣（LeetCode）

考虑到每一个位置能存储的水量和左右两边的最高高度，以及自身的高度相关，所以先遍历一遍用 dp 算出来，最后累加答案即可。

class Solution:
    def single_trap(self, height: int, max_l: int, max_r: int):
        if height >= max_l or height >= max_r:
            return 0
        else:
            return min(max_l, max_r) - height
    def trap(self, height: List[int]) -> int:
        max_l_height = [0] * len(height)
        max_r_height = [0] * len(height)
        for i in range(1, len(height)):
            max_l_height[i] = max(max_l_height[i - 1], height[i - 1])
            max_r_height[len(height) - 1 - i] = max(height[len(height) - i], max_r_height[len(height) - i])
        ans = 0
        for i in range(len(height)):
            ans += self.single_trap(height[i], max_l_height[i], max_r_height[i])
        return ans