6.三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
class Solution:
def threeSum(self, nums : List[int]) -> List[List[int]]:
# 存储最终结果
res = []
# 数组长度小于3，直接返回空（凑不出三元组）
if len(nums) < 3:
return res
# 第一步：排序（核心操作，既方便找数又方便去重）
nums.sort()
# 第二步：遍历每个数作为三元组的第一个数
for i in range(len(nums)):
# 优化：如果第一个数已经大于0，后面的数都更大，和不可能为0，直接结束循环
if nums[i] > 0:
break
# 去重：如果当前数和前一个数一样，跳过（避免重复的三元组）
if i > 0 and nums[i] == nums[i - 1]:
continue
# 左指针：第一个数的下一个数
left = i + 1
# 右指针：数组最后一个数
right = len(nums) - 1
# 第三步：双指针找另外两个数
while left < right:
# 计算三数之和
total = nums[i] + nums[left] + nums[right]
if total == 0:
# 找到符合条件的三元组，加入结果
res.append([nums[i], nums[left], nums[right]])
# 去重：左指针跳过重复的数（比如[0,0,0]，避免重复加）
while left < right and nums[left] == nums[left + 1]:
left += 1
# 去重：右指针跳过重复的数
while left < right and nums[right] == nums[right - 1]:
right -= 1
# 移动指针，继续找下一组
left += 1
right -= 1
elif total < 0:
# 和太小，左指针右移（找更大的数）
left += 1
else:
# 和太大，右指针左移（找更小的数）
right -= 1
return res
if __name__ == '__main__':
solution = Solution()
nums = [-1, 0, 1, 2, -1, -4]
result = solution.threeSum(nums)
print(result)7.接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
题解：
1.左右两个指针，更新最大高度
2.接水量=左右指针的最大高度-当前高度
def trap(height):
# 边界条件：数组长度小于3，无法形成凹槽接水
if len(height) < 3:
return 0
# 初始化指针和最大高度、总雨水量
left = 0 # 左指针：从最左边开始
right = len(height) - 1 # 右指针：从最右边开始
left_max = 0 # 左指针左侧（包括自己）的最大高度
right_max = 0 # 右指针右侧（包括自己）的最大高度
total_water = 0 # 总接水量
# 双指针向中间遍历，直到相遇
while left < right:
# 更新左右侧的最大高度（当前指针位置的高度可能刷新最大值）
left_max = max(left_max, height[left])
right_max = max(right_max, height[right])
# 核心逻辑：哪边的最大高度更小，就计算哪边的接水量
if left_max < right_max:
# 左指针位置能接的水量 = 左侧最大高度 - 当前柱子高度
total_water += left_max - height[left]
left += 1 # 左指针右移
else:
# 右指针位置能接的水量 = 右侧最大高度 - 当前柱子高度
total_water += right_max - height[right]
right -= 1 # 右指针左移
return total_water
# 测试示例
if __name__ == "__main__":
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
print(trap(height)) # 输出：68.无重复字符串的最长子串
题解：
1.集合去重
2.右指针遍历字符串，作为华东窗口，如果当前字符已在窗口中，不断右移左指针，直到移除重复字符
3.将当前字符加入到字符串，计算长度右指针-左指针+1，更新最大长度
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 用集合存储当前窗口内的字符，快速判断是否重复
char_set = set()
# 左指针，初始化为0（滑动窗口的左边界）
left = 0
# 记录最长子串的长度
max_len = 0
# 右指针遍历字符串，作为滑动窗口的右边界
for right in range(len(s)):
# 如果当前字符已在窗口中，不断右移左指针，直到移除重复字符
while s[right] in char_set:
char_set.remove(s[left])
left += 1
# 将当前字符加入窗口
char_set.add(s[right])
# 计算当前窗口长度，更新最大长度
current_len = right - left + 1
if current_len > max_len:
max_len = current_len
return max_len
# 测试用例
if __name__ == "__main__":
solution = Solution()
test_cases = [
("abcabcbb", 3),
]
for s, expected in test_cases:
result = solution.lengthOfLongestSubstring(s)
print(f"输入: {s!r} | 预期输出: {expected} | 实际输出: {result} | {'通过' if result == expected else '失败'}")9.
- THE END -
最后修改：2025年12月31日
非特殊说明，本博所有文章均为博主原创。
如若转载，请注明出处：https://blog.grover.top/2024/08/30/leetcode_hot_6-10/
共有 0 条评论