Coding Puzzles, 2nd edition: Thinking in code

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2 Solve this problem
[Thoughts] There are three sorts of solutions: The first solution is hashing. Scan the array from the left to the right, and store the number and its index(the original index in the array) in the map. Then, scan the array again with the help of map. The time complexity is O(n). The second solution is two-pointer scanning. Sort the array first, unfortunately, you need to remember the original index during sorting.

Its better to use a new object to hold the number-index mapping.After the array is sorted, then, use two pointers to scan from two bounds to the middle. Find the solution and return their original index. The time complexity is O(n*lgn). Note: Two-pointers Scanning Two-pointer is a optimized way to search targets on top of a SORTED array. One pointer points to the head of the sorted array, and the other one points to the tail of the sorted array. The two points move towards the middle of the array until they meet.

The third solution is brute-force searching. This is the most obvious solution, but with the highest time complexity O(n*n)
[Code]
Following is the execution of solution 1 : 1: vector twoSum(vector &numbers, int target) { 2: map mapping; 3: vector result; 4: for(int i =0; i< numbers.size(); i++) 5: { 6: mapping[numbers[i]]=i; 7: } 8: for(int i =0; i< numbers.size(); i++) 9: { 10: int searched = target - numbers[i]; 11: if(mapping.find(searched) != mapping.end()) 12: { 13: result.push_back(i+1); 14: result.push_back(mapping[searched]+1); 15: break; 16: } 17: } 18: return result; 19: } Solution 2: 1: struct Node 2: { 3: int val; 4: int index; 5: Node(int pVal, int pIndex):val(pVal), index(pIndex){} 6: }; 7: static bool compare(const Node &left, const Node &right) 8: { 9: return left.val < right.val; 10: } 11: vector twoSum(vector &numbers, int target) { 12: vector elements; 13: for(int i =0; i< numbers.size(); i++) 14: { 15: elements.push_back(Node(numbers[i], i)); 16: } 17: std::sort(elements.begin(), elements.end(), compare); 18: int start = 0, end = numbers.size()-1; 19: vector result; 20: while(start < end) 21: { 22: int sum = elements[start].val + elements[end].val; 23: if(sum == target) 24: { 25: result.push_back(elements[start].index+1); 26: if(elements[start].index < elements[end].index) 27: result.push_back(elements[end].index+1); 28: else 29: result.insert(result.begin(), elements[end].index+1); 30: break; 31: } 32: else if(sum > target) 33: end--; 34: else 35: start++; 36: } 37: return result; 38: }
Solution 3: two nested loop. The implementation of the solution is left out here.