LeetCode1_ Sum of two numbers

Original article , Reprint please indicate the source .

Topic type ： Simple type

The title is as follows

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

 The first is the easiest to think of , Ideas ： Two layers of for loop , Enumerate all the situations , Find subscript .
 But the time complexity is O(n^2),  Spatial complexity O(1)

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

See the above Time complexity O(n^2), n= The length of the array , The space complexity is O(1)
leetcode Execution score of

Then I thought of trading space for time , So there is a second solution

solution 2

 Ideas ： Use one map/unordered_map, here unordered_map be better than map, Then it will traverse once vector, In the process of traversal, each value is 8 reduce ,
 Then judge what is after subtraction , Then take the number after subtraction map Of key Inside looking for .
 If you find , So we found , The first subscript is map This key Corresponding value(key save vector Value ,value Save subscript );
 On the contrary, if it is not found , take vector[i] Add to map Of key On ,value yes i.

map Achieved Red and black trees
Time complex reading O(logn), because map Lookup 、 Delete 、 Increase the time complexity of a series of operations such as stable , All for logn
Complex reading space O(n)
unordered_map Achieved Hashtable
Time complex reading O(c-n), lookup 、 Delete 、 It's fast to add , The time complexity is constant O
Complex reading space O(n)
because unordered_map Internally based on hash table , With （key,value） Store in the form of pairs , So the occupancy rate is high Unordered_map Lookup 、 Delete 、 The added time complexity is unstable , Average is O, Depending on the hash function . In extreme cases it could be O(n)
Look at the diagram

Code implementation map Of

class Solution {
    
public:
	// The second solution .key=value value=index
	vector<int> twoSum(vector<int>& nums, int target) {
    
		std::map<int, int> contentmap;
		for (int i = 0; i < nums.size(); i++)
		{
    
			int less = target - nums[i];
			map<int, int>::iterator iter;
			iter = contentmap.find(less);
			if (iter != contentmap.end())
			{
    
				return {
     contentmap[less], i };
			}
			else
			{
    
				contentmap[nums[i]] = i;//.insert(pair(nums[i], i));
			}
		}
		return {
    };
	}
};

Code implementation unordered_map Of , This solution is better than that based on map Solution

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

leetcode Execution score of

I hope I can work out a better solution

thank you , It's not easy to create , Great Xia, please stay … Move your lovely hands , Give me a compliment before you go <(￣︶￣)>