# LeetCode题目：Two Sum

By | 2012 年 11 月 1 日

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

### 代码：16ms过大集合

```class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> ret;
if(numbers.size() <= 1) return ret;
//find min/max for trim
int vmin = numbers[0];
int vmax = numbers[0];
for(int i = 1; i < numbers.size(); ++i) {
if(numbers[i] < vmin)
vmin = numbers[i];
if(numbers[i] > vmax)
vmax = numbers[i];
}
for(int i0 = 0; i0 < numbers.size() - 1; ++ i0) {
int v0 = numbers[i0];
int starget = target - v0;
if(starget < vmin || starget > vmax) continue;
for(int i1 = i0 + 1; i1 < numbers.size(); ++ i1) {
if(numbers[i1] == starget) {
ret.push_back(i0 + 1);
ret.push_back(i1 + 1);
return ret;
}
}
}
return ret;
}
};
```

### New C++ solution

```// new C++ solution using map updated 2016-04-22
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int, int> valueIndexMap;
for(int i = 0; i < nums.size(); i++)
valueIndexMap[nums[i]] = i;
vector<int> indices;
for(int i = 0; i < nums.size(); i++) {
int remain = target - nums[i];
if(valueIndexMap.find(remain) != valueIndexMap.end() && valueIndexMap[remain] != i){
indices.push_back(i);
indices.push_back(valueIndexMap[remain]);
return indices;
}
}
return indices;
}
};
```

### new Ruby solution

```# ruby solution updated 2016-04-22
def two_sum(nums, target)
map = {}
nums.each_with_index{|v,i| map[v] = i}
nums.each_with_index do |v,i|
remain = target - v
if (ri = map[remain]) != nil && i != ri
return [i, ri]
end
end
end
```

### new Java solution

```// Java solution update 2016-04-22
public class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 0 ; i < nums.length; i++){
map.put(nums[i], i);
}
int[] result = new int[2];
for(int i = 0 ; i < nums.length; i++){
int remain = target - nums[i];
if(map.containsKey(remain)){
int ri = map.get(remain);
if(i != ri){
result[0] = i;
result[1] = ri;
break;
}
}

}
return result;
}
}
```

### new C solution updated 2016-04-22

```/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target) {
int * results = malloc(sizeof(int) * 2);
bool found = false;
for(int i = 0 ; i < numsSize && !found; ++i)
for(int j = i+1 ; j < numsSize && !found; ++j){
if(nums[i]+nums[j] == target){
results[0] = i;
results[1] = j;
found = true;
}
}
return results;
}
```

## 7 thoughts on “LeetCode题目：Two Sum”

1. uniEagle Post author

作弊应该不算，题目上也没有严格要求。只不过hashmap的解法需要很多额外空间。

1. uniEagle Post author

哦，对哦，那就是hashmap好了。O(n)空间O(n)时间；如果排序方法的话，那是O(n)空间O(nlogn)时间不划算了。