LeetCode - 1 : Two Sums

Let's discuss the 'Two Sums' problem on LeetCode.
The problem link can be found here

Brute Force Approach [O(n²)]

1. Create an integer vector (res) to store the indices.
2. Iterate the given array for all the possible index combinations, such that indices are different.
3. Add the numbers at these two indices at check if it equal to target
4. If equal, push the indices into the res vector and break the loop.
5. Return the res vector.

vector<int> twoSum(vector<int>& nums, int target) {        
        //Brute Forece Apprach
        vector<int> res;
        for(int i=0;i<nums.size();++i){
            for(int j=i+1;j<nums.size();++j){
                if(nums[i]+nums[j]==target){
                    res.push_back(i);
                    res.push_back(j);
                    break;
                }
            }
            if(res.size()==2){
                break;
            }
        }
        return res;        
    }

Optimized Approach [O(n)]

1. Create integer vector to store the result.
2. Create a hash table.
3. Iterate through the _nums_ vector.
1. Find the difference between _target_ and current element.
2. Check if the difference value exists in the hash table.
3. If it does, push the current index and index value from the hash to the vector and return the vector.
4. If it does not, then push difference as the key and index as the value in the hash table and continue

 unordered_map<int,int> map;
        vector<int> res;
        for(int i=0;i<nums.size();++i){
            if(map.find(target-nums[i])!=map.end()){
                res.push_back(i);
                res.push_back(map[target-nums[i]]);
                return res;
            }
            map[nums[i]] = i;
        }
        return res;