两数之和
leetcode题目两数之和
思路讲解
使用一个辅助哈希表，对数组进行遍历，遍历每一项时都判断target-nums[i]是否都在遍历中遇到过（其中i是当前索引值），如果是，则直接返回，如果不是，则记录到辅助哈希表中{nums[i]: i}，然后继续遍历。
解题代码
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:mapper = {} # 存储 数字 -> 索引 的映射for i, num in enumerate(nums):complement = target - numif complement in mapper:# 返回顺序：先找到的索引在前，当前索引在后return [mapper[complement], i]# 存储当前数字和它的索引mapper[num] = ireturn [] # 根据题目假设，总会有一个解，这行不会执行
三数之和
leetcode题目三数之和
思路讲解
先对原数组进行一次排序，然后一层循环固定一个元素，循环内部利用双指针找出剩下的两个元素。还要注意去重。
解题代码
class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums.sort()res = []n = len(nums)# 边界条件：如果数组长度小于3，直接返回空列表if n < 3:return resfor i in range(n-2):# 去重：跳过相同的固定元素if i > 0 and nums[i] == nums[i-1]:continue# 优化：如果最小的三个数之和都大于0，直接退出if nums[i] + nums[i+1] + nums[i+2] > 0:break# 优化：如果当前数加上最大的两个数都小于0，跳过当前数if nums[i] + nums[n-2] + nums[n-1] < 0:continuel = i + 1r = n - 1while l < r:total = nums[i] + nums[l] + nums[r]if total < 0:l += 1elif total > 0:r -= 1else:res.append([nums[i], nums[l], nums[r]])# 跳过左边相同的元素while l < r and nums[l] == nums[l+1]:l += 1# 跳过右边相同的元素while l < r and nums[r] == nums[r-1]:r -= 1# 移动指针寻找新的组合l += 1r -= 1return res