1. Two Sum

Question

LeetCode Problem

Given an integer array nums and an integer target, return indices of the two numbers such that they add up to target. Each input has exactly one solution, and you may not use the same element twice. Return the answer in any order.

Constraints

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Exactly one valid answer exists.

Solutions

Brute Force

Pick up any pair of integer in the array and sum them up. Then check if the summary equals to target.^[1]

vector<int> twoSum(vector<int> &arr, int target) {
	int N = arr.size();
	vector<int> ret;
	for (int i = 0; i < (N-1); i++) {
		for (int j = i+1; j < N; j++) {
			int sum = arr[i] + arr[j];
			if (sum == target) {
				ret.push_back(i);
				ret.push_back(j);
				return ret;
			}
		}
	}
	ret.assign(0, 2);
	return ret;
}

Hash Table

Solution: Iterate over the array and use hashtable to store the difference between target and current value as the key, and put the current index as the value. ^[2] Once array's value meet one of the key in the hashtable, we now find the solution.

vector<int> twoSum(vector<int> &nums, int target) {
	unordered_map<int, int> map;
	for (int i = 0; i < nums.size(); ++i) {
		if (map.count(nums[i]) > 0) {
			return vector<int>{map[nums[i]], i};
		}
		map[target - nums[i]] = i;
	}
	return vector<int>{-1, -1};
}

Analysis