两数之和：暴力枚举与哈希表优化

暴力枚举思路

解决两数之和最直接的办法就是双重循环。对于数组里的每个数字 x，我们尝试在剩余部分寻找 target - x。

这里有个小细节：当遍历到位置 i 时，i 之前的元素其实已经和 i 匹配过了，所以内层循环从 i + 1 开始即可。同时题目保证有解且每个元素只能用一次，所以不需要担心重复使用同一个下标。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

这种写法逻辑简单，但效率不高。最坏情况下需要比较 N*(N-1)/2 次，时间复杂度是 O(N²)。好在空间上只用了几个变量，额外空间是 O(1)。

哈希表优化思路

既然瓶颈在于查找 target - x 太慢，能不能把查找速度提上来？哈希表正好能解决这个问题。

我们在遍历数组的过程中，一边检查'之前有没有出现过 target - 当前值'，一边把当前值存入哈希表。这样查找就变成了 O(1) 操作。关键是插入时机：必须先查后存，防止自己和自己匹配。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
             (hashtable.containsKey(target - nums[i])) {
                  []{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
          [];
    }
}