# Two Sum

## Question

### Problem Statement

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**].

## 题解1 - 哈希表

### Python

class Solution:
"""
@param numbers : An array of Integer
@param target : target = numbers[index1] + numbers[index2]
@return : [index1 + 1, index2 + 1] (index1 < index2)
"""
def twoSum(self, numbers, target):
hashdict = {}
for i, item in enumerate(numbers):
if (target - item) in hashdict:
return (hashdict[target - item] + 1, i + 1)
hashdict[item] = i

return (-1, -1)

### C++

class Solution {
public:
/*
* @param numbers : An array of Integer
* @param target : target = numbers[index1] + numbers[index2]
* @return : [index1+1, index2+1] (index1 < index2)
*/
vector<int> twoSum(vector<int> &nums, int target) {
vector<int> result;
const int length = nums.size();
if (0 == length) {
return result;
}

// first value, second index
unordered_map<int, int> hash(length);
for (int i = 0; i != length; ++i) {
if (hash.find(target - nums[i]) != hash.end()) {
result.push_back(hash[target - nums[i]]);
result.push_back(i + 1);
return result;
} else {
hash[nums[i]] = i + 1;
}
}

return result;
}
};

### Java

public class Solution {
public int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length == 0) return null;

Map<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
int index1 = 0, index2 = 0;
for (int i = 0; i < nums.length; i++) {
if (hashmap.containsKey(target - nums[i])) {
index1 = hashmap.get(target - nums[i]);
index2 = i;
return new int[]{index1, index2};
} else {
hashmap.put(nums[i], i);
}
}

return null;
}
}

### 源码分析

1. 异常处理。
2. 使用 C++ 11 中的哈希表实现unordered_map映射值和索引。Python 中的dict就是天然的哈希表。
3. 找到满足条件的解就返回，找不到就加入哈希表中。注意题中要求返回索引值的含义。

## 题解2 - 排序后使用两根指针

### C++

class Solution {
public:
/*
* @param numbers : An array of Integer
* @param target : target = numbers[index1] + numbers[index2]
* @return : [index1+1, index2+1] (index1 < index2)
*/
vector<int> twoSum(vector<int> &nums, int target) {
vector<int> result;
const int length = nums.size();
if (0 == length) {
return result;
}

// first num, second is index
vector<pair<int, int> > num_index(length);
// map num value and index
for (int i = 0; i != length; ++i) {
num_index[i].first = nums[i];
num_index[i].second = i + 1;
}

sort(num_index.begin(), num_index.end());
int start = 0, end = length - 1;
while (start < end) {
if (num_index[start].first + num_index[end].first > target) {
--end;
} else if(num_index[start].first + num_index[end].first == target) {
int min_index = min(num_index[start].second, num_index[end].second);
int max_index = max(num_index[start].second, num_index[end].second);
result.push_back(min_index);
result.push_back(max_index);
return result;
} else {
++start;
}
}

return result;
}
};

### 源码分析

1. 异常处理。
2. 使用length保存数组的长度，避免反复调用nums.size()造成性能损失。
3. 使用pair组合排序前的值和索引，避免排序后找不到原有索引信息。
4. 使用标准库函数排序。
5. 两根指针指头尾，逐步靠拢。