LeetCode 1：兩數之和——哈希表單次遍歷查找目標配對

題目描述

給定整數數組 nums 和目標值 target，找出兩數下標使其和為 target。假設唯一解，下標從 1 開始。

哈希表解法

遍歷數組，對每個 x 查找 target - x 是否已在表中。若存在直接返回；否則將 x 存入表。時間 O(n)，空間 O(n)。

C++ 實現

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> pos;  // 值 -> 索引(0-based)
        for (int i = 0; i < nums.size(); ++i) {
            int need = target - nums[i];
            if (pos.count(need)) return {pos[need]+1, i+1};
            pos[nums[i]] = i;
        }
        return {};
    }
};

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 need = target - nums[i];
            if (map.containsKey(need)) return new int[]{map.get(need)+1, i+1};
            map.put(nums[i], i);
        }
        return new int[0];
    }
}

關鍵點

• 單次遍歷同時完成查找與建表，避免兩次遍歷。
• unordered_map 平均 O(1) 查找/插入。
• 下標 +1 滿足題目 1-based 要求。

複雜度

• 時間：O(n) 平均。
• 空間：O(n)。