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, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]
Difficulty:Easy
解法一
最简单的解法当然是遍历数组两次，这样不管怎样都能找到两个值加起来等于目标值，不过复杂度略高，为 O(n2) ，因此省略代码。
解法二
另一种解法就是排序后通过二分查找。
int bSearch(vector<int>& arr, int left, int right, int target) { while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == target) return mid; else if (arr[mid] > target) right = mid - 1; else if (arr[mid] < target) left = mid + 1; } return -1; } vector<int> twoSum(vector<int>& nums, int target) { vector<int> arr(nums); sort(arr.begin(), arr.end()); int right = -1; int left = -1; for (int i = 0; i < arr.size(); i++) { right = bSearch(arr, i, arr.size() - 1, target - arr[i]); if (right != -1) { left = i; break; } } /*由于这里求的下标是排序之后的下标，因此要映射回去*/ int r_left = -1; int r_right = -1; for (int i = 0; i < nums.size(); i++) { if (nums[i] == arr[left] || nums[i] == arr[right]) { r_left = r_left == -1 ? i : r_left; r_right = r_left != i && r_left != -1 ? i : r_right; } if (r_left != -1 && r_right != -1) break; } vector<int> result = { r_left,r_right }; return result; }代码排序的复杂度为 O(nlogn) ，而对 n 个数进行n次二分查找的复杂度也为 O(nlogn) ，这样总的复杂度就为 O(nlogn) 。
解法三
当然，如果用哈希表的话，步骤会简单很多，因为只需要遍历整个数组，将数组值和下标放入哈希表中，然后如果目标值和当前值的差值在哈希表中有记录，就找到了两个值的和为目标值的下标了。
vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> numMap; vector<int> result; for (int i = 0; i < nums.size(); i++) { if (numMap[target - nums[i]]) { result.push_back(numMap[target - nums[i]] - 1); result.push_back(i); break; } numMap[nums[i]] = i + 1; } return result; }代码的时间复杂度为 O(n) 。
总结
总的来说，使用哈希表，当然是最快的，不过一开始没有想到这个解法，反而挑了一个最繁琐的。究其原因，是没有利用遍历得到的额外信息，因为遍历到每一个数字，除了知道数字本身的价值外，还能知道这个数字需要的另一个数字。利用这个额外信息，就能明显减少代码的时间复杂度。
