001. Two Sum

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.

Example:

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

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


Questions:

1. whether there is only one solution if the question does not declare it.


Test Cases:

1. [2, 7, 11, 15] 9
2. [11, 2, 15, 7] 9
3. [2, 7] 9
4. [2, 4, 4, 3] 8

Solution 1:
Data structure:
array, unordered_map
Method:
hash table
Steps:
1. for each number, lookup target-number in the hash table
2. if it is in the hash table, return result, else insert it in the hash table.
Complexity:
runtime: O(N)
space: O(N)
Code:
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
       unordered_map<int, int> my_map;
       vector<int> res;
       for (int i = 0; i < nums.size(); i++) {
           int numToFind = target - nums[i];
           if (my_map.find(numToFind) != my_map.end()) {
               res.push_back(my_map[numToFind]);
               res.push_back(i);
               return res;
           }
           my_map[nums[i]] = i;
       }
       return res;
    }
};

Solution 2:

Data structure:
array
Method:
two pointers
Steps:
1. copy out the array
2. sort the array
3. iterate from beginning and end, and find the two integers
4. iterate through the original array, and find the two indexes
Complexity:
runtime: O(NlogN)
space: O(N)
Code:
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> cp(nums);
        sort(cp.begin(), cp.end());
        vector<int> results;
        int n = nums.size();
        if (!n) return results;
        int left = 0, right = n - 1;
        while (left < right) {
            if (cp[left] + cp[right] == target) break;
            else if (cp[left] + cp[right] < target) left++;
            else right--;
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] == cp[left]) results.push_back(i);
            else if (nums[i] == cp[right]) results.push_back(i);
            if (results.size() == 2) break;
        }
        return results;
    }
};

Solution 3:

Data structure:
array
Method:
brute force
Steps:
1. two nested loops to find the two nums.
Complexity:
runtime: O(N^2)
space: O(1)
Code:
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> results;
        int n = nums.size();
        if (!n) return results;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    results.push_back(i);
                    results.push_back(j);
                    return results;
                }
            }
        }
        return results;
    }
};

Things to learn:
1. copy an array: vector cp(nums).
2. the element using iterator: iter = num.end() – 1
3. unordered_map.find() complexity: average constant, worst linear.