博文中会简要介绍Leetcode P0001题目分析及解题思路。

“Two Sum”是一道很经典的题目，在Amazon的面试中出现比较多，题干直白易懂。在数组中找到两个数使其加和为target。

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

为了在将复杂度控制O(n)，需要思考如何记忆已经查询过的数，否则就会需要重复查询。简单来讲就是cache思维，以空间换时间。将已经查询过的数记忆在某个数据结构X中，然后每次在数组中新查询一个数都在X内查找是否有加和为target的数。

由于返回的是下标，所以自然想到用键值对来存储，所以数据结构X则是HashTable。

以下是Java的题解代码实现。

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

以下是C++的题解代码实现。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> num2index_map;
        for (int idx=0; idx<nums.size(); ++idx) {
            if (num2index_map.count(target-nums[idx]) > 0) {
                return {num2index_map[target-nums[idx]], idx};
            }
            num2index_map[nums[idx]] = idx;
        }
                
        return vector<int>();
    }
};