Leecode01. Sum of two numbers -- leecode100 hot questions series

I'm Xiao Zhang , Determined to use the most concise code to do the most efficient expression


The following is my personal solution , Each problem includes all solutions as much as possible , And achieve the optimal solution , Welcome to collect ! Leaving a message. !

Portal ——>Leecode Big factory hot topic 100 Tao series problem solution


Given an array of integers nums And an integer target value target, Please find... In the array And is the target value target the Two Integers , And return their array subscripts .

You can assume that each input corresponds to only one answer . however , The same element in the array cannot be repeated in the answer .

You can return the answers in any order .

Example 1:
Input :nums = [2,7,11,15], target = 9
Output :[0,1]
explain : because nums[0] + nums[1] == 9 , return [0, 1] .

Example 2:
Input :nums = [3,2,4], target = 6
Output :[1,2]

Example 3:
Input :nums = [3,3], target = 6
Output :[0,1]

Tips :
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109

There will only be one valid answer
Advanced : You can come up with a time complexity less than O(n2) The algorithm of ?


solution 1: violence

Time complexity O(n²), Spatial complexity O(1)

class Solution {

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

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

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

if(nums[i] + nums[j] == target) {

res.push_back(i);
res.push_back(j);
goto loop;
}
}
}
loop:;
return res;
}
};

solution 2:hash surface

Time complexity O(n), Spatial complexity O(n)

class Solution {

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

unordered_map<int, int>um;
for(int i = 0; i < nums.size(); i++) {

auto it = um.find(target - nums[i]);
if(it != um.end()) {

return {
it->second, i};
}
um[nums[i]] = i;
}
return {
};
}
};
Please bring the original link to reprint ,thank
Similar articles

2021-10-14

2021-10-14

2021-10-14

2021-10-14

2021-10-14

2021-10-14

2021-10-14

2021-10-14

2021-10-14

2021-10-14

2021-10-14

2021-10-14

2021-10-14