Force buckle: 1-sum of two numbers

Title Description

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

Their thinking

The first thing I think of when I see this problem is violence , Direct two layers for Circulation can solve the problem , The time complexity is O(n²), Violence can generally be done , I'm not going to repeat it here . So here is the second idea , Use hash table to do this problem , The time complexity of hash table is only O(1), First floor for Circulation can solve , stay O(n) You can solve this problem with the complexity of

We know that hash table is a mapping relationship , That is, key value pairs , So let's go through the array , Take the value of the array as the key of the hash table , The subscript of the array is mapped as the value of the hash table . Then traverse the array again , We need to determine whether there is a corresponding value in the hash table plus the value of the current array equals target, And pay attention to one condition ： The answer cannot appear in the same element , So this requires us to exclude the current element .

Code implementation

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int a,b;
        // Create hash table 
        unordered_map<int,int>q;
        for(int i=0;i<nums.size();i++)
        q[nums[i]]=i;
        for(int i=0;i<nums.size();i++)
        {
            // Judge whether there is a corresponding value and exclude the value of the current array 
            if(q.count(target-nums[i])!=0&&q[target-nums[i]]!=i)
            {
                a=i,b=q[target-nums[i]];
                break;
            }
        }
        return {a,b};
    }
};