1.Two Sum(Leetcode note)

Topics : easy , Array , Hash Table

Input: 1.array of integers nums. 2.an integer target.

Output: return indices of the two numbers such that they add up to target.

Example: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Approach

solution 1:(Brute Force)

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

Complexity Analysis

• Time complexity: O(n²)
• Space complexity: O(1)

solution 2:(Two-pass Hash Table)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target){
        unordered_map<int,int>hashmp;
        for(int i = 0; i<nums.size();i++){
            hashmp[nums[i]] = i;
        }
        for(int i = 0; i < nums.size(); i++){
            int com = target - nums[i];
            if(hashmp.find(com) != hashmp.end() && hashmp[com] != i){
                return{i, hashmp[com]};
            }
        }
        //no vaild pair, return an empty 
        return {};
    }
};

Complexity Analysis

• Time complexity: O(n).
• Space complexity: O(n).

solution 3:(one-pass Hash Table)

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 complement = target - nums[i];
            if(hash.find(complement) != hash.end()){
                return {hash[complement] ,i};
            }
            hash[nums[i]] = i;
        }
        return {};
    }
};

Complexity Analysis

• Time complexity: O(n). The solution is faster than Two pass.
• Space complexity: O(n).