56. Two Sum【easy】

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 zero-based.

Notice

You may assume that each input would have exactly one solution

Example

numbers=[2, 7, 11, 15], target=9

return [0, 1]

Challenge

Either of the following solutions are acceptable:

O(n) Space, O(nlogn) Time
O(n) Space, O(n) Time

题意

给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。

你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。

解法一：

 1 class Solution {
 2 public:
 3     /*
 4      * @param numbers: An array of Integer
 5      * @param target: target = numbers[index1] + numbers[index2]
 6      * @return: [index1 + 1, index2 + 1] (index1 < index2)
 7      */
 8     vector<int> twoSum(vector<int>& nums, int target) {
 9         // hash[i]表示nums中数值为i的下标
10         unordered_map<int, int> hash;
11         vector<int> result;
12 
13         // 一边循环每个数，一边加入hash表。
14         for (int i = 0; i < nums.size(); i++) {
15             if (hash.find(target - nums[i]) != hash.end()) {
16                 // target - nums[i]的下标更小，放在前面
17                 result.push_back(hash[target - nums[i]]);
18                 result.push_back(i);
19                 return result;
20             }
21             hash[nums[i]] = i;
22         }
23 
24         // 无解的情况
25         result.push_back(-1);
26         result.push_back(-1);
27         return result;
28     }
29 };

使用万能的hash，参考@NineChapter 的代码

解法二：

 1 class Solution {
 2 public:
 3     /*
 4      * @param numbers: An array of Integer
 5      * @param target: target = numbers[index1] + numbers[index2]
 6      * @return: [index1 + 1, index2 + 1] (index1 < index2)
 7      */
 8     vector<int> twoSum(vector<int> &numbers, int target) {
 9         int len = numbers.size();
10         int i, j;
11         int flag = 0;//flag作为找到答案后跳出的一个标记用变量
12         for (i = 0; i < len; ++i) {
13             for (j = i + 1; j < len; ++j) {
14                 if (numbers[i] + numbers[j] == target) {
15                     flag=1;
16                     break;
17                 }
18             }
19             if (flag)
20                 break;
21         }
22 
23         vector<int> ans;
24         ans.push_back(i);
25         ans.push_back(j);
26 
27         return ans;
28     }
29 };

暴力破解法，完全不推荐