1.两数之和

题目描述：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

我写的版本：从两边往中间查找。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []
        Flag = False
        for i in range(len(nums)):
            for j in range(len(nums)-1, -1, -1):
                if i == j:
                    break
                if (nums[i] + nums[j]) == target:
                    result.append(i)
                    result.append(j)
                    Flag = True
                    return i, j
                    break
            if Flag:
                break

官方题解

暴力枚举。解答中第二层循环为什么要从i+1开始

1. 避免重复使用同一元素
题目明确要求不能重复使用同一元素。如果第二次循环从 0开始，当 j = i 时，会导致 nums[i] + nums[j] 实际是 2 * nums[i]，此时若 target = 2 * nums[i]，代码会错误地将同一元素用两次。
例如：数组 [3, 2, 4]，target = 6。若 j 从 0 开始，当 i = 0 时，j = 0 会导致误判 3 + 3 = 6（但第二个 3 不存在）。

从 i + 1 开始，保证了 j 始终在 i 之后，物理上排除重复使用同一元素的可能性。

2. 避免重复检查已匹配的组合
假设数组为 [a, b, c, d]，当 i = 0 时，j 会遍历 1, 2, 3，检查组合 (a+b, a+c, a+d)。
当 i = 1 时，若 j 仍从 0 开始，会再次检查 (b+a, b+c, b+d)，但 a+b 和 b+a 是同一对元素，导致重复计算。

从 i + 1 开始，确保每个元素对只被检查一次，将时间复杂度从 O(n²) 优化到实际的 O(n²/2)。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        
        return []

哈希表。这个是以空间换时间，利用哈希表存储元素，空间复杂度为O(n)。将“查找 target - x”的时间复杂度从 O(n) 降到了 O(1)，整体时间复杂度优化到 O(n)。为什么“先检查，再插入”？避免元素自匹配：假设 target = 2x，如果先插入 x 再检查，哈希表中会存在 x，导致错误地将同一个元素用两次。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []