Leetcod#1: Two sum

(improved solution)

language: C++

key idea: STL map

map use:

1. define -- map<key, value>

2. find -- map.find(key)

code:

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

vector<int> ans;

map<int,int> table;

for(int i=0; i<nums.size();i++){

int res = target - nums[i];

map<int,int>::iterator it = table.find(res);

if(it != table.end()){

return vector<int>({it->second,i});

}

table[nums[i]] = i;

}

return ans;

}

};

Time complexity: O(n) (hash table search time:O(1))

Space complexity: O(n) - nums stored in the hash table