《算法通关之路》跟练——第二章数学之美（一）

两数之和

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 - num
            if complement in mapper:
                # 返回顺序：先找到的索引在前，当前索引在后
                return [mapper[complement], i]
            # 存储当前数字和它的索引
            mapper[num] = i
        return []  # 根据题目假设，总会有一个解，这行不会执行

三数之和

leetcode题目三数之和

思路讲解

先对原数组进行一次排序，然后一层循环固定一个元素，循环内部利用双指针找出剩下的两个元素。还要注意去重。

解题代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        n = len(nums)

        # 边界条件：如果数组长度小于3，直接返回空列表
        if n < 3:
            return res

        for 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:
                continue

            l = i + 1
            r = n - 1
            while l < r:
                total = nums[i] + nums[l] + nums[r]
                if total < 0:
                    l += 1
                elif total > 0:
                    r -= 1
                else:
                    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 += 1
                    r -= 1
        return res