two sum – leetcode a1

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.

The return format had been changed to zero-based indices.

• zero-based indices.
• [1, 3, 4, 2]. 4 + 2 = 6 is ok. But not for 3 + 3 = 6.
• [1, 3, 3, 2]. 3 + 3 = 6 is ok.

Loop through each element x and find if there is another value equals to target - x.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
 		int length = nums.size();
 		for (int i = 0; i < length; i++) 
 			for (int j = i + 1; j < length; j++) {
 				if (nums[i] + nums[j] == target) {
 					ans.push_back(i);
 					ans.push_back(j);
 					return ans;
 				}
 			}
 		return ans;
	};
};

Complexity: O(n^2).

One way to improve the brute force is sort the whole array and loop through each element x and find if there is another value equals to target - x by binary search.

Complexity: O(nlogn).

While we iterate and inserting elements into the hash table, we also look back to check if current element’s complement already exists in the table. If it exists, we have found a solution and return immediately.

16 / 16 test cases passed.
Status: Accepted
Runtime: 26 ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        int length = nums.size();
        map<int, int>mp;
        for (int i = 0; i < length; i++) {
        	if (mp[target - nums[i]]) {
        		ans.push_back(mp[target - nums[i]] - 1);
        		ans.push_back(i);
        		return ans;
        	}
        	mp[nums[i]] = i + 1;
        }
 	   return ans;
	};
};

Complexity: O(n).