# 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

## ไปฃ็ 

### Approach #1 Brute Force

``````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.

``````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

``````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 nn 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.

``````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)};
}
}
}
}``````

Last updated