[LeetCode]1 Two Sum/两数之和

2018-08-02

写在最前面：

最近开始刷LeetCode上的题目了，做个记录吧，希望刷完之后自己的代码水平能有所提升。

之前都是习惯用JAVA写，但是C++也要练，同时还要注意时间复杂度，之前都没有做好。

★

Two Sum

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.

两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

对于这个题目，首先想到的是暴力搜索，但是时间复杂度很高，为O(n^2) 。

另一个想法是，遍历一个数字，用目标去减得到另一个数字，查找这个数字是否存在。其中需要解决的是：1、查找，采用HashMap将数与位置映射起来（HashMap是常数级的查找效率） 2、重复，需要记录位置信息，两个不能一样。

java：

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();//映射
    int[] res = new int[2];//存放结果
    for (int i = 0; i < nums.length; ++i) {
        m.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; ++i) {
        int t = target - nums[i];
        if (m.containsKey(t) && m.get(t) != i) {
            res[0] = i;
            res[1] = m.get(t);
            break;
        }
    }
    return res;
}

（感觉这个映射，Integer，如果值相同，只能记录一个位置，最后的）

C++：

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> m;
    vector<int> res;
    for (int i = 0; i < nums.size(); ++i) {
        m[nums[i]] = i;
    }
    for (int i = 0; i < nums.size(); ++i) {
        int t = target - nums[i];
        if (m.count(t) && m[t] != i) {
            res.push_back(i);
            res.push_back(m[t]);
            break;
        }
    }
    return res;
}

C++用得不是很熟，hashmap不大会，还有vector用得也不多，希望多写写熟练一下。