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 {
};
}
};