Leetcode - > 1 sum of two numbers

1） Sum of two numbers

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 ：

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

Method 1 ： Violence enumeration

1. Enumerate all different combinations of two subscripts in the array
2. Check whether the sum of their corresponding numbers is equal to target

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), here n Is array length , In the worst case, any two numbers in the array must be matched once .
• Spatial complexity ：O(1), Only constants and temporary variables are used

#include <vector>
#include <iostream>
using namespace std;

class Solution {
    
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
    
            for (int j = i + 1; j < n; ++j) {
    
                if (nums[i] + nums[j] == target) {
    
                    return {
    i, j};
                }
            }
        }
        return {
    };
    }
};

int main()
{
    
	int target = 9;
	Solutiont two;
	
	vector<int> arr = {
     2, 7, 11, 15};
	
	cout << "[" << two.twoSum(arr, target)[0] << ","<<two.twoSum(arr, target)[1] << "]" << endl;
	//pause();
	return 0;
}

Method 2 ： Hashtable
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) Down to 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 .

#include <iostream> 
#include <unordered_map> 
#include <vector>
using namespace std; 

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

int main()
{
    
	int target = 9;
	Solution two;
	
	vector<int> arr = {
     2, 7, 11, 15};
	
	cout << "[" << two.twoSum(arr, target)[0] << ","<<two.twoSum(arr, target)[1] << "]" << endl;
	//pause();
	return 0;
}

Complexity analysis

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

Spatial complexity ：O(N), among N Is the number of elements in the array . Mainly for the cost of hash table .

Notes ：

1） When vector When input to a function as a formal parameter , There are two ways ：

vector<int>& nums;
vector<int> nums;

belt & Indicates that the passed in function is vector References to （ Physical location ）, Function internal pair vector changes ,vector Will change ;
No & It means that what is passed in is vector Replica （ Opened up another location ）, Internal changes to the function , Will not affect the original vector;
namely
vector nums：nums Is a container variable , The name of the container is vector, The data in the container memory is int type
vector &nums：nums For a quote , The quoted content is vector The integer data stored inside this container

vector Please refer to ：https://www.runoob.com/w3cnote/cpp-vector-container-analysis.html

2）linux Run under c++ The program , I hope the console will not disappear immediately after output .

stay windows Under the system , Use the following statement ：

#include

system(“pause”);

Found in linux There will be errors like this in the system , This is because linux incognizance system(“pause”); This statement , Change it to ：

#include <unistd.h>

pause();

Can be in linux The effect of retaining the console under the system .

3）unordered_map

Unordered mapping （Unordered maps） Is an associated container for storing elements composed of key values and mapping values , And allows quick retrieval of individual elements based on their keys . stay unordered_map in , Key values are often used to uniquely identify elements , The mapping value is the object with the content associated with the key . The type of key and the value of the mapping may be different .

unordered_map A hash table is implemented internally （ Also called a hash table , By mapping key values to Hash A location in the table to access records , The time complexity of searching can reach O(1), It is widely used in massive data processing ）. therefore , The order of its elements is out of order .

And map contrast

map

 advantage ：

 Orderliness , This is a map The biggest advantage of structure , The order of its elements will simplify many operations in many applications ;

 Red and black trees , The internal implementation of a red black tree makes map Many of the operations in O(lgn) It can be realized under the time complexity of , So it's very efficient .

 shortcoming ： High occupancy of space , because map Red black tree is realized internally , Although it improves the operation efficiency , But because each node needs to save an additional parent node 、 Children and red / Black property , So that each node occupies a lot of space 

 Application scenarios ： For those questions with sequence requirements , use map It will be more efficient 

unordered_map

 advantage ： Because the hash table is implemented internally , So the search speed is very fast 
 shortcoming ： It takes a lot of time to build a hash table 
 Application scenarios ： For finding problems ,unordered_map It will be more efficient , So there's a search problem , I often think about using unordered_map

summary

 The problem of memory occupancy is transformed into a red black tree  VS Hash surface , still unordered_map It takes up a lot of memory ;
 however unordered_map Execution is more efficient than map Much higher ;
 about unordered_map or unordered_set Containers , The traversal order is not necessarily the same as the order entered when the container was created , Because traversal is in accordance with the hash table traversal from front to back .

Use ：
unordered_map Usage and map It's the same , Provides insert,size,count Wait for the operation , And the elements inside are also in the form of pair Type to store . Its underlying implementation is completely different , The above has explained , But it is consistent in terms of external use .

#include <iostream> 
#include <unordered_map> 
#include <map>
#include <string> 
using namespace std;  
int main()  
{
      
	// Be careful ：C++11 To support bracket initialization 
    unordered_map<int, string> myMap={
    {
     5, " Zhang Da " },{
     6, " Li Wu " }};// Use {} assignment 
    myMap[2] = " Li Si ";  // Use [ ] Make a single insert , If the key value already exists 2, Then the assignment is modified , If not, insert .
    myMap.insert(pair<int, string>(3, " Chen er "));// Use insert and pair Insert 
  
	// Traverse the output + The use of iterators 
    auto iter = myMap.begin();//auto Automatically recognized as iterator type unordered_map<int,string>::iterator
    while (iter!= myMap.end())
    {
      
        cout << iter->first << "," << iter->second << endl;  
        ++iter;  
    }  
	
	// Find the element and output + The use of iterators 
    auto iterator = myMap.find(2);//find() Return a point 2 The iterator 
    if (iterator != myMap.end())
	    cout << endl<< iterator->first << "," << iterator->second << endl;  
    system("pause");  
    return 0;  
}  

Output ：

3, Chen er 
2, Li Si 
5, Zhang Da 
6, Li Wu 

2, Li Si