🧮 Week 1 · Day 2 — LeetCode Hot 100 学习笔记
🩵 最长回文子串 (Longest Palindromic Substring)
🧠 题目描述
给你一个字符串 s，请找出 s 中最长的 回文子串。
示例
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
💡 解法思路：中心扩展法（奇偶分离）
回文串具有“对称性”。
可从每个字符（奇数中心）或每对字符（偶数中心）向两侧扩展，寻找最长回文。
思路步骤
-
遍历字符串，以每个字符或字符对为“中心”；
-
向两边扩展，直到左右字符不相等；
-
记录并更新当前最长的回文范围；
-
分别处理奇数长度与偶数长度的回文。
💻 代码实现
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n == 0:
return ""
ans_left = ans_right = 0
# 奇数长度中心扩展
for i in range(n):
l = r = i
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
l += 1
r -= 1
if r - l > ans_right - ans_left:
ans_left, ans_right = l, r
# 偶数长度中心扩展
for i in range(n - 1):
l, r = i, i + 1
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
l += 1
r -= 1
if r - l > ans_right - ans_left:
ans_left, ans_right = l, r
return s[ans_left:ans_right + 1]
⏱️ 复杂度分析
💧 盛最多水的容器 (Container With Most Water)
🧠 题目描述
给定一个长度为 n 的整数数组 height，其中每个元素代表一条竖线的高度。
找到两条线，使得它们与 x 轴构成的容器可以 盛最多的水。
示例
输入：height = [1,8,6,2,5,4,8,3,7]
输出：49
💡 解法思路：双指针夹逼法
面积 = 宽 × 高
高度由 较短的那根线 决定。
每次移动较短的一边，尝试寻找更高的线，从而可能得到更大面积。
思路步骤
-
初始化左右指针
left=0,right=n-1 -
计算当前面积，更新最大值；
-
移动较短的边：
-
若左边较短 →
left += 1 -
否则 →
right -= 1
-
-
直到
left >= right。
💻 代码实现
from typing import List
class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
max_area = 0
while left < right:
area = (right - left) * min(height[left], height[right])
max_area = max(max_area, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
⏱️ 复杂度分析
🔺 三数之和 (3Sum)
🧠 题目描述
给定一个整数数组 nums，返回所有不重复的三元组 [nums[i], nums[j], nums[k]]，
使得 nums[i] + nums[j] + nums[k] == 0。
示例
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
💡 解法思路：排序 + 双指针
思路步骤
-
对数组进行排序；
-
遍历每个元素
nums[i]作为三元组首元素；-
若
nums[i] > 0，后续无法为 0； -
若与前一个元素相同则跳过；
-
-
使用双指针
j、k在[i+1, n-1]范围内搜索：-
若和大于 0，
k -= 1 -
若和小于 0，
j += 1 -
若等于 0，加入答案并跳过重复元素。
-
💻 代码实现
from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
ans = []
for i in range(n - 2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
j, k = i + 1, n - 1
while j < k:
s = nums[i] + nums[j] + nums[k]
if s > 0:
k -= 1
elif s < 0:
j += 1
else:
ans.append([nums[i], nums[j], nums[k]])
# 跳过重复
while j < k and nums[j] == nums[j + 1]:
j += 1
while j < k and nums[k] == nums[k - 1]:
k -= 1
j += 1
k -= 1
return ans