Solution to LeetCode Problems: Two Sum

Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Thoughts:

 

If the array is not sorted, then the brutal way time complexity is O(n^2) = n(n-1).

When treating search problem, sorting is usually helpful. After sort, we can use two pointers pointing at the beginning and the end of the array. If the sum of numbers at two pointers larger than target, left-move the pointer at right; otherwise right-move the pointer at last until the solution is found, which the problem ensured.

The algorithm has time complexity O(nlogn) + O(n) = O(nlogn). The first term is for sorting, and the second term is for searching. Before we sort, we need to record the original indices for each elements, this will require an extra O(2n) space complexity.

Solution：

1. class Solution {  
2. public:  
3.     typedef pair<int, size_t> valoffset_pair_t;  
4.       
5.   
6.     vector<int> twoSum(vector<int> &numbers, int target) {  
7.   
8.         vector<valoffset_pair_t> new_array;  
9.         // Preallocate the memory for faster push_back  
10.         new_array.reserve(numbers.size());  
11.           
12.         // generate the new array  
13.         int index=0;  
14.         for(auto i : numbers)  
15.             new_array.push_back(valoffset_pair_t(i, ++index));  
16.             // Note: here the index is already increased, so   
17.             // the new indices are not zero based  
18.           
19.         // sort it!  
20.         sort(begin(new_array), end(new_array),   
21.             [&](const valoffset_pair_t& v1, const valoffset_pair_t& v2) -> bool  
22.             {  
23.                 return v1.first < v2.first;  
24.             }  
25.         );  
26.           
27.         // now find the right pair using two pointers  
28.         auto p_left=begin(new_array);  
29.         auto p_right=end(new_array);   
30.         p_right--;  // make it locate at the last position  
31.         int sum = p_left->first + p_right->first;  
32.           
33.         // it is guaranteed to have one exact solution  
34.         while(sum!=target)  
35.         {  
36.             sum = p_left->first + p_right->first;  
37.             if (sum > target)  
38.                 p_right--;  
39.             else if (sum < target)  
40.                 p_left++;  
41.             else  
42.                 break;  
43.         }  
44.         return vector<int>(  
45.             {min(p_left->second, p_right->second),  
46.              max(p_left->second, p_right->second)});  
47.     }  
48. };