Leetcode 1-sum of two numbers

Want to make APP Same thing as WeChat , Can run small programs smoothly ？ | Experience will send you to Xinjiang 、 Huawei 、 Cherry keyboard ！>>>

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[0] + nums[1] = 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 .