1、两数之和
题目描述：
给定一个整数数组
nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]
解题
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: #字典用于存储元素值和索引的映射 num_map = {} #遍历数组 for i,num in enumerate(nums): #计算差值 complement = target - num if complement in num_map: return [num_map[complement],i] num_map[num] = i
2、两数相加
题目描述：
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0] 输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]
解题
class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: dummy = ListNode(0) # 创建哑节点 current = dummy # 当前节点指针 carry = 0 # 进位值 # 当两个链表有任一非空或还有进位时继续 while l1 or l2 or carry: # 获取当前位的值 val1 = l1.val if l1 else 0 val2 = l2.val if l2 else 0 total = val1 + val2 + carry carry = total // 10 # 计算当前位的进位 digit = total % 10 # 计算当前位的总和 # 创建新节点并连接 current.next = ListNode(digit) current = current.next # 移动原始链表指针 if l1: l1 = l1.next if l2: l2 = l2.next return dummy.next # 返回结果链表的头节点
3、无重复字符的最长子串
题目描述：
给定一个字符串s请你找出其中不含有重复字符的最长的长度。
示例 1:
输入:s = "abcabcbb" 输出:3 解释: 因为无重复字符的最长子串是"abc"，所以其长度为 3。
示例 2:
输入:s = "bbbbb" 输出:1 解释:因为无重复字符的最长子串是"b"，所以其长度为 1。
示例 3:
输入:s = "pwwkew" 输出:3 解释:因为无重复字符的最长子串是"wke"，所以其长度为 3。 请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。
解题：
滑动窗口（双指针）
- 双指针维护无重复窗口：
left- 子串起始位置right- 当前遍历位置
- 字符位置存储：
char_index记录每个字符最后出现的位置- 遇到重复字符时，直接将窗口跳到该字符上次出现位置之后
- 窗口大小计算：
- 当前窗口长度 =
right - left + 1 - 每次迭代更新最大长度
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: char_index = {} # 存储字符最后出现位置的字典 max_len = 0 # 最大长度 left = 0 # 滑动窗口左边界 for right, char in enumerate(s): # 如果字符已存在且在窗口内，移动左边界 if char in char_index and char_index[char] >= left: left = char_index[char] + 1 # 更新字符位置 char_index[char] = right # 更新最大长度 max_len = max(max_len, right - left + 1) return max_len
4、寻找两个正序数组的中位数
题目描述：
给定两个大小分别为
m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为
O(log (m+n)) 。示例 1：
输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
题解：时间复杂度
O(log(m+n)) 采用二分法排序from typing import List class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: # 确保 nums1 是较短的数组 if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1 m, n = len(nums1), len(nums2) total_left = (m + n + 1) // 2 # 左半部分元素数量 # 在 nums1 中进行二分查找 [0, m] left, right = 0, m while left <= right: # i 是 nums1 的分割点，j 是 nums2 的分割点 i = (left + right) // 2 j = total_left - i # 处理边界条件 nums1_left_max = -10**6 - 1 if i == 0 else nums1[i-1] nums1_right_min = 10**6 + 1 if i == m else nums1[i] nums2_left_max = -10**6 - 1 if j == 0 else nums2[j-1] nums2_right_min = 10**6 + 1 if j == n else nums2[j] # 验证分割是否有效 if nums1_left_max <= nums2_right_min and nums2_left_max <= nums1_right_min: # 找到中位数 max_left = max(nums1_left_max, nums2_left_max) min_right = min(nums1_right_min, nums2_right_min) return (max_left + min_right) / 2.0 if (m + n) % 2 == 0 else max_left # 调整二分边界 elif nums1_left_max > nums2_right_min: right = i - 1 else: left = i + 1 return 0.0
题解：时间复杂度
O((m+n)) 采用冒泡排序class Solution: def findMedianSortedArrays(self, nums1: list, nums2: list) -> float: # 合并数组 nums = nums1 + nums2 n = len(nums) # 空数组处理 if n == 0: return 0.0 # 冒泡排序（O(n²)） for i in range(n): swapped = False for j in range(n-i-1): if nums[j] > nums[j+1]: nums[j], nums[j+1] = nums[j+1], nums[j] # 修正变量名 swapped = True if not swapped: break # 计算中位数 if n % 2 == 1: median = nums[n//2] # 直接使用 n//2 索引 else: left_mid = nums[n//2 - 1] right_mid = nums[n//2] median = (left_mid + right_mid) / 2 # 使用浮点除法 return float(median)
5、最长回文子串
题目描述：
给你一个字符串
s，找到s中最长的。示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
题解：中心扩展法
def longest_palindromic_substring(s: str) -> str: """中心扩展法（时间复杂度 O(n²)，空间复杂度 O(1)）""" def expand_center(left: int, right: int) -> str: """从中心向两侧扩展寻找最长回文子串""" while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return s[left + 1:right] # 返回最大回文子串 if not s: return "" longest = "" for i in range(len(s)): # 奇数长度回文（以单个字符为中心） pal_odd = expand_center(i, i) # 偶数长度回文（以两个字符之间的空为中心） pal_even = expand_center(i, i + 1) if i + 1 < len(s) else "" # 更新最长回文串 longest = max([longest, pal_odd, pal_even], key=len) return longest