# 1.Two-Sum

## 1. Two Sum

## 题目地址

<https://www.lintcode.com/problem/two-sum/description>

<https://leetcode.com/problems/two-sum/>

## 题目描述

```
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:
2 <= nums.length <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.
```

## 代码

### Approach #1 Brute Force

```java
class Solution {
  public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
      for (int j = i + 1; j < nums.length; j++) {
        if (nums[j] == target - nums[i]) {
          return new int[] {i, j};
        }
      }
    }

    return null;
  }
}
```

### Approach 1: One-pass Hash Table

It turns out we can do it in one-pass. While we iterate and inserting elements into the table, we also look back to check if current element's complement already exists in the table. If it exists, we have found a solution and return immediately.

```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 - numsp[i]);
        index2 = i;
        return new int[]{index1, index2};
      } else {
        hashmap.put(nums[i], i);
      }
    }

    return null;
  }
}
```

### Approach 2: Sort

对数组进行排序，然后使用binary search搜索target

```cpp
class Solution {
  public:
        vector<int> twoSum(vector<int> &num, int target) {
        vector<int> result;
        const int length = nums.size();
        if (0 == length) return result;
        // map num value and index
        vector<pair<int, int>> num_index(length);
        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) {
          int s = num_index[start].first + num_index[end].first;
          if (s > target) {
            --end;
          } else if (s == 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;
      }
}
```

### Approach 3: Two-pass Hash Table

**Complexity Analysis:**

* Time complexity : O(n). We traverse the list containing n*n* elements exactly twice. Since the hash table reduces the look up time to O(1), the time complexity is O(n).
* Space complexity : O(n). The extra space required depends on the number of items stored in the hash table, which stores exactly n elements.

```java
class Solution {
  public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
      map.put(nums[i], i);
    }

    for (int i = 0; i < nums.length; i++) {
      int complement = target - nums[i];
      if (map.containsKey(complement) && map.get(complement) != i) {
        return new int[] {i, map.get(complement)};
      }
    }
  }
}
```