分析

• 本题的考点：哈希表。

• 哈希表中存储的(key, val)表示：（数据，该数据对应对应的下标）。

• 假设当前遍历的是元素nums[i]，我们需要到哈希表中查询是否存在target-nums[i]，如果存在的话，返回答案；否则将当前数据插入哈希表，继续遍历，直到得到答案。

代码

• C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++) {
            int r = target - nums[i];
            if (hash.count(r)) return {hash[r], i};
            hash[nums[i]] = i;
        }
        return {};  // 题目保证有解，一定不会执行这句话
    }
};

• Java

class Solution {
    public int[] twoSum(int[] nums, int target) {

        HashMap<Integer, Integer> hash = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int r = target - nums[i];
            if (hash.containsKey(r)) return new int[]{hash.get(r), i};
            hash.put(nums[i], i);
        }
        return new int[]{};  // 题目保证有解，一定不会执行这句话
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为数组长度。因为哈希表的操作都是$O(1)$的，且只有一重循环。

• 空间复杂度：$O(n)$，n为数组长度。哈希表需要占用$O(n)$的空间。