leetcode. 1 --- sum of two numbers

Violence solution

direct 2 layer for Circular violence search , The time complexity is O(n^2)

The code is as follows :

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

Use hash table

Define a r = target - nums[i], See if you can find this element in the hash table , If it exists, return the element and subscript , Otherwise, it will be stored in the hash table .

The code is as follows :

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

Time complexity :O(n)
Spatial complexity :O(n)