Leetcode Study Day 20

Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we 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]
 

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

My solution

My first idea is to use two for loops to loop through the array and find the two numbers. However, this method is not efficient. The time complexity is O(n^2).

Then I found a better solution. I use a unordered_map to store the numbers and their indices. Then I loop through the array and check if the target minus the current number is in the map. If it is, then we find the two numbers. If it is not, we put the current number and its index into the map.

What I learnt today:

1. I can insert multiple numbers into a vector at the same time:

   list.insert(list.end(), {element,element});

Full code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map <int, int> map;
        vector <int> ans;
        for (int i = 0; i< nums.size(); i++){
            int plusNo = target - nums[i];
            if (map.find(plusNo) != map.end()){
                ans.insert(ans.end(), {i,map[plusNo]});
                return ans;
            }
            map[nums[i]] = i;
        }
        return ans;
    }
};