C++ two solutions, sort O(nlogn) and hashmap O(n)

• sort the array, find the two values, then find the index. Time complexity O(nlogn), space complexity O(n).

Because the sort() will change the indexes of the num, we need a backup of data, which costs extra space.

``````vector<int> twoSum(vector<int>& nums, int target) {
vector<int> nums_temp = nums;
sort(nums_temp.begin(),nums_temp.end());
vector<int> res;
int i=0,j=nums_temp.size()-1;
while(i<j){
if (nums_temp[i]+nums_temp[j]==target){
for (int k=0;k<nums.size();k++){
if (nums[k]==nums_temp[i] || nums[k]==nums_temp[j]){
res.push_back(k);
}
}
break;
}else if (nums_temp[i]+nums_temp[j]>target){
j--;
}else{
i++;
}
}
return res;
}
``````

or we can use hash map, time complexity O(n), space complexity O(n)

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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.