1.Two Sum

Tags:easy Array

Links: https://leetcode.com/problems/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.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

---

Answer:

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

        for (int i = 0; i < nums.size(); ++i)
            mapping[nums[i]] = i;

        for (int i = 0; i < nums.size(); ++i){
            int tmp = target - nums[i];
            if(mapping.find(tmp) != mapping.end() && mapping[tmp] != i){
                result.push_back(i);
                result.push_back(mapping[tmp]);
                break;
            }
        }

        return result;
    }
};

解析：如果采用双循环暴力求解，复杂度是$O(n)$，采用hash法，复杂度是$O(n)$，这里注意第12行增加了一个判断条件，因为可能存在这样一种特例，如[3,2,4]，target是6，不增加mapping[tmp] != i则返回[0,0]，增加后返回[1,2].