题目链接

1. 两数之和

解题思路

遍历数组时，用哈希表保存已经出现过的数字及其下标。对于当前数字 nums[i]，计算目标补数 target - nums[i]：

  • 如果补数已经在哈希表中，直接返回补数的下标和当前下标。
  • 如果补数尚未出现，将当前数字和下标放入哈希表，继续遍历。

先查找、后写入，可以避免同一个元素被使用两次。

复杂度

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

Java 解答

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

复盘

这道题的关键是把“寻找另外一个数”转换成 O(1) 平均复杂度的哈希查询。哈希表中只保存当前位置之前的元素，因此命中时得到的两个下标天然不同。