力扣hot100题python

### 力扣（LeetCode）热门100题的Python解法 #### 两数之和 (Two Sum) 对于经典的`two sum`问题，一种暴力求解方法如下所示： ```python class Solution(object): def twoSum(self, nums, target): for i in range(0, len(nums)-1): for j in range(i+1, len(nums)): if (target == nums[i] + nums[j]): return [i, j] return [] ``` 这种方法的时间复杂度为O(n²)，适用于较小规模的数据集[^1]。 #### 组合总和 (Combination Sum) 针对组合总和的问题，可以采用回溯算法来解决。下面是一个简单的实现例子： ```python def combinationSum(candidates, target): result = [] def backtrack(start, path, remain_target): if remain_target == 0: result.append(path[:]) return elif remain_target < 0: return for i in range(start, len(candidates)): path.append(candidates[i]) backtrack(i, path, remain_target - candidates[i]) path.pop() backtrack(0,[],target) return result ``` 这段代码通过递归的方式探索所有可能的解决方案，并记录下符合条件的结果集合[^2]。 #### 最长连续序列 (Longest Consecutive Sequence) 为了找到数组中最长的连续元素序列，可以通过哈希表优化查找过程： ```python from typing import List class Solution: def longestConsecutive(self, nums: List[int]) -> int: longest_streak = 0 nums_set = set(nums) for num in nums_set: if num-1 not in nums_set: current_num = num current_streak = 1 while current_num + 1 in nums_set: current_num += 1 current_streak += 1 longest_streak = max(longest_streak, current_streak) return longest_streak ``` 此方案利用了集合快速查询的特点，使得时间复杂度降低至接近线性级别[^3]。 #### 字符串中的字母异位词 (Find All Anagrams in a String) 寻找给定模式的所有变位词位置时，滑动窗口技术非常有效率： ```python import collections def findAnagrams(s,p): need, window = {}, {} for c in p: need[c] = need.get(c, 0)+1 left,right = 0,0 valid = 0 res = [] while right<len(s): c = s[right] right+=1 if c in need: window[c]=window.get(c,0)+1 if window[c]==need[c]: valid+=1 while right-left>=len(p): if valid==len(need): res.append(left) d=s[left] left+=1 if d in need: if window[d]==need[d]: valid-=1 window[d]-=1 return res ``` 上述函数实现了固定长度窗口内的字符频率匹配逻辑，从而高效定位目标子串的位置. #### 两数相加 (Add Two Numbers) 当处理链表形式的大整数加法运算时，可以从低位向高位逐位计算并考虑进位情况： ```python # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: dummy_head = ListNode() curr_node = dummy_head carry_over = 0 while l1 is not None or l2 is not None or carry_over != 0: digit_1 = l1.val if l1 else 0 digit_2 = l2.val if l2 else 0 total_digits = digit_1 + digit_2 + carry_over carry_over = total_digits // 10 new_digit = total_digits % 10 curr_node.next = ListNode(new_digit) curr_node = curr_node.next l1 = l1.next if l1 else None l2 = l2.next if l2 else None return dummy_head.next ``` 该段程序模拟手工算术的过程，特别适合于大数值之间的精确计算操作[^4].