力扣-两数之和（力扣两数之和答案java）

首发地址：https://www.xichunling.com/?p=42

解法一

两层循环，时间复杂度O(n^2)，空间复杂度O(1)。

执行时间244ms，内存消耗9.3MB。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret;
        int len = nums.size();
        for (int i = 0; i < len; i ++) {
            for (int j = i + 1; j < len; j ++) {
                if (target - nums[i] == nums[j]) {
                    ret.insert(ret.begin(), i);
                    ret.insert(ret.begin()+ 1, j);
                    break;
                }
            }
            if (ret.size() == 2) {
                break;
            }
        }
        return ret;
    }
};

解法二

map记录数组元素与下标的映射关系，遍历一遍数组求解。时间复杂度O(n)，空间复杂度O(n)。

执行时间20ms，内存消耗10.1MB。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret;
        map<int, int> mapnum;
        int len = nums.size();
        for (int i = 0; i < len; i ++) {
            int key = target - nums[i];
            map<int, int>::iterator it = mapnum.find(key);
            if (it == mapnum.end()) {
                mapnum.insert(pair<int, int>(nums[i], i));
            } else {
                ret.insert(ret.begin(), mapnum.find(key)->second);
                ret.insert(ret.begin() + 1, i);
                break;
            }
        }

        return ret;
    }
};

解法三

用unordered_map构造映射，比map更快。因为map是用红黑树实现的，数据插入里面会排好序，搜索过程的时间复杂度为O(logn)。而unordered_map是用哈希表实现的，查找元素的时间复杂度为O(1)。

map适用于对内存大小敏感或数据要求有序性的情况；unordered_map适用于对查询效率要求较高的情况。

总得来说，这种解法的时间复杂度O(n)，空间复杂度O(n)。耗时4ms，内存消耗10.3MB。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret;
        unordered_map<int, int> unorderedmap;
        int len = nums.size();
        for (int i = 0; i < len; i ++) {
            unorderedmap[nums[i]] = i;
        }
        for (int i = 0; i < len; i ++) {
            int key = target - nums[i];
            if (unorderedmap.count(key) && unorderedmap[key] != i) {
                ret.push_back(i);
                ret.push_back(unorderedmap[key]);
                break;
            }
        }

        return ret;
    }
};