# [LeetCode] 1. Two Sum（两数之和）

• Difficulty: Easy

• Related Topics: Array, Hash Table

## Description

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.

## Examples

### 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 <= 10^5

• -10^9 <= nums[i] <= 10^9

• -10^9 <= target <= 10^9

• Only one valid answer exists

## Hints

1. A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it‘s best to try out brute force solutions for just for completeness. It is from thses brute force solutions that you can come up with optimizations.

一个真的很暴力的方案是遍历数组内可能的元素对，那样真的太慢了。但，最好还是用暴力法先把这题过了。在暴力求解的过程中，自然就能想到优化方案。

2. so, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y which is value - x, where value is the input parameter. Can we change our array somehow so that this search becomes faster?

所以，如果我们固定一个数（记为 x），我们需要扫描整个数组去寻找一个 y，其中 ytarget - x。我们能否修改数组使得这一搜索变得更高效？

3. The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

第二种想法是，不改变原有数组，我们能否使用一点额外空间？比如使用哈希表加速查找？

## Solution

class Solution {
fun twoSum(nums: IntArray, target: Int): IntArray {
// 建立从数组元素到元素下标的映射
val map = hashMapOf<Int, Int>()

for (i in nums.indices) {
// 对于数组中的每个元素
// 我们找另一个对应的元素（target - nums[i]）是否出现过
// 出现过即为所求
if (map.containsKey(target - nums[i])) {
return intArrayOf(map.getValue(target - nums[i]), i)
}
// 没出现过，将当前元素和对应下标存入 map（可能与之匹配的元素在这之后）
map[nums[i]] = i
}

// 题目说解一定存在，所以这一句实际上并不会执行
return intArrayOf(-1, -1)
}
}


[LeetCode] 1. Two Sum（两数之和）

(0)
(0)