Day One

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Naive way is to use two for loop and scan the list and its time complexity is O(n^2) and n is the length of given array.

But since we need to find only one pair numbers whose summation equals to the target value. Scan the list only once will do:

• Build a map with key set to the value of each element from the list, and map value set to each element's location accordingly (time complexity O(n))

• Scan the list, and with current value, find an element in the rest of the list that has value == (target - current). (time complexity O(n))

Data Structure:
Use a map to record the value and its index in the list.
Key is the element value, and value is the index of the element

Python

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums:
            return []
        
        nums_dict = {v: k for k, v in enumerate(nums)}
        print(nums_dict)
        for index, num in enumerate(nums):
            value = target - num
            if value in nums_dict and nums_dict[value] != index: # do not include self
                return [index, nums_dict.get(target-num)]
        return []

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numsMap;
        for(int i=0; i<nums.size(); i++){
            numsMap[nums[i]] = i;
        };// build the map
        
        for(int i=0; i< nums.size(); i++){
          int value = target - nums[i];
          if(numsMap.count(value) > 0 && i != numsMap[value]){//check if key exist in the map
              vector<int> result;
              result.push_back(i);
              result.push_back(numsMap[value]);
              return result;
          }; 
              
        };
    }
};