Two Sum

Problem: Given an array of integers numbers 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 <= 104
  -109 <= nums[i] <= 109
  -109 <= target <= 109
```
  Only one valid answer exists. Follow-up: Can you come up with an algorithm that is less than O(n²) time complexity?
Solution 最初的想法是暴力破解，两次for循环，找到能match target的两个numbers。但为了保证算法时间复杂度，HashMap的插入和查找速度是O(1), 所以利用HashMap进行一次查找，会使算法时间复杂度降低一个维度。思维为：
- 把数组内所有的数都存入HashMap, key为数值，value为index。算法时间复杂度O(n)
- 从头到为遍历数组，在HashMap中去找是否存在target - 数组中当前的数值。算法时间复杂度O(n)
- 如果存在且和当前数组不是同一个值的情况下即为结果，返回对饮索引
- 注意的是要判断边界条件及不能为同一数值
```
public int[] twoSum(int[] nums, int target) {
  if(nums == null || nums.length < 2) {
   return null;
  }
  int[] res = new int[2];
  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 value = target - nums[i];
   if(map.containsKey(value) && i != map.get(value)) {
       res[0] = i;
       res[1] = map.get(value);
       return res;
   }
  }
  return res;
}
```

Two Sum

Two Sum

FEATURED TAGS

FRIENDS