# Leetcode 1-sum of two numbers

2020-11-10 08:39:55

# Title Description

Given an array of integers and a target value , Find the two numbers in the array that are the target values .
You can assume that each input corresponds to only one answer , And the same elements cannot be reused .
Example :

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

because  nums + nums = 2 + 7 = 9
So back  [0, 1]
``````

## Method 1

Violence enumeration

``````class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int length=nums.size();
vector<int> result;
for(int i=0;i<length;i++)
{
for(int j=i+1;j<length;j++)
{
if(target==nums[i]+nums[j])
{
result.push_back(i);
result.push_back(j);
break;

}

}

}
return result;

}
};
``````

Ideas and algorithms
The easiest way to think of is to enumerate every number in an array x, Look for the existence of target - x.
When we look for target - x when , It needs to be noted that each is located in x All the previous elements have been associated with x Matched , So there's no need to match again . And each element cannot be used twice , So we just need to x Look for... In the following elements target - x.

Complexity analysis

• Time complexity ：O(N^2)O(N2）, among NN Is the number of elements in the array . In the worst case, any two numbers in the array must be matched once .
• Spatial complexity ：O(1)O(1).

## Method 2

Hashtable

``````class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashtable;
for (int i = 0; i < nums.size(); ++i) {
auto it = hashtable.find(target - nums[i]);
if (it != hashtable.end()) {
return {it->second, i};
}
hashtable[nums[i]] = i;
}
return {};
}

};
``````

Ideas and algorithms

Note that the reason for the high time complexity of method 1 is to find target - x The time complexity of is too high . therefore , We need a better approach , Can quickly find whether the target element exists in the array . If there is , We need to find out its index .

Use hash table , You can look for target - x The time complexity is reduced to from O(N)O(N) Down to O(1)O(1).

So we create a hash table , For each of these x, We first query the hash table for the presence of target - x, And then x Insert into hash table , You can guarantee that you won't let x Match yourself .

Complexity analysis

• Time complexity ：O(N)O(N), among NN Is the number of elements in the array . For each element x, We can O(1)O(1) Looking for target - x.
• Spatial complexity ：O(N)O(N), among NN Is the number of elements in the array . Mainly for the cost of hash table .