原始链接：[力扣题解最佳实践 - 力扣人](https://leetcoder.net/zh/leetcode/1-two-sum)

力扣链接：[1. 两数之和](https://leetcode.cn/problems/two-sum) ，难度：**简单**。

给定一个整数数组`nums` 和一个整数目标值`target`，请你在该数组中找出**和为目标值**`target` 的那**两个** 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

**输出**:`[0,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 these brute force solutions that you can come up with optimizations.

</details>

<details>

<summary>提示 2</summary>

提示 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?

</details>

<details>

<summary>提示 3</summary>

提示 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?

</details>

1. 暴力解法的时间复杂度为`O(n**2)`，想提升效率，可以对数组进行排序，然后用双指针，一个指向数组头，一个指向数组尾，根据**和**情况决定`left += 1`还是`right -= 1`。

2.对数值数组排序后，想知道某个数值对应的原来的索引下标，有两种方案：

2.对数字数组排序后，如果想知道某个值对应的原始`index`，有两种解决方案：

- 方案1：使用index() 查找；

- 方案2：在排序时带上索引下标，即排序的对象是元组`(num,index)`的数组。

- 方案1：排序时带上`index`，即排序的对象是`(num, index)`的元组数组。这个技巧**必须掌握**，因为很多题目都会用到。

- 方案2：用`index()`方法去找。我在另一个解法中讨论过这个问题。

1.`Map`中，`key`是`num`，`value`是数组`index`。

2. 遍历数组，如果`target - num`在`Map`中，返回。反之，将`num`加入`Map`中。

1.`Map`中，`key`是`num`，`value`是数组`index`。

- 空间复杂度：`O(N)`。

let numToIndex=newMap()

for (let i=0; i<nums.length; i++) {

numToIndex.set(nums[i], i)

}

```

2. 遍历数组，如果`target - num`在`Map`中，返回。反之，将`num`加入`Map`中。

## 复杂度

* 时间：`O(n)`。

* 空间：`O(n)`。

classSolution:

deftwoSum(self,nums: List[int],target:int) -> List[int]:

num_index_list= [(num, i)for i, numinenumerate(nums)]

num_index_list.sort()

left=0

right=len(nums)-1

while left< right:

sum_= num_index_list[left][0]+ num_index_list[right][0]

if sum_== target:

return [num_index_list[left][1], num_index_list[right][1]]

if sum_< target:

left+=1

right-=1

## Java

### Solution1: Two pointers

### Solution2: UsingMap

1. 在`Map`中，`key`是`num`，`value`是数组`index`。

2. 遍历数组，如果`target - num`在`Map`中，就返回它。否则，把`num`加入`Map`。

1. 在`Map`中，`key`是`num`，`value`是数组`index`。

let numToIndex=newMap()

for (let i=0; i<nums.length; i++) {

numToIndex.set(nums[i], i)

}

2. 遍历数组，如果`target - num`在`Map`中，就返回它。否则，把`num`加入`Map`。

let numToIndex=newMap()

for (let i=0; i<nums.length; i++) {

if (numToIndex.has(target- nums[i])) {// 1

return [numToIndex.get(target- nums[i]), i]// 2

}

numToIndex.set(nums[i], i)

}

- 时间复杂度：`O(N)`。

- 空间复杂度：`O(N)`。

classSolution {

publicint[]twoSum(int[]nums,inttarget) {

var numToIndex=newHashMap<Integer,Integer>();

for (var i=0; i< nums.length; i++) {

if (numToIndex.containsKey(target- nums[i])) {

returnnewint[]{numToIndex.get(target- nums[i]), i};

### Solution1: Two pointers

### Solution2: UsingMap

classSolution:

deftwoSum(self,nums: List[int],target:int) -> List[int]:

num_to_index= {}

for i, numinenumerate(nums):

if target- numin num_to_index:

return [num_to_index[target- num], i]

### Solution1: Two pointers

### Solution2: UsingMap

classSolution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

unordered_map<int, int> num_to_index;

### Solution1: Two pointers

### Solution2: UsingMap

vartwoSum=function (nums,target) {

let numToIndex=newMap()

for (let i=0; i<nums.length; i++) {

if (numToIndex.has(target- nums[i])) {

return [numToIndex.get(target- nums[i]), i]

### Solution1: Two pointers

### Solution2: UsingMap

publicclassSolution {

publicint[]TwoSum(int[]nums,inttarget) {

varnumToIndex=newDictionary<int,int>();

for (inti=0;i<nums.Length;i++) {

if (numToIndex.ContainsKey(target-nums[i])) {

return [numToIndex[target-nums[i]],i];

### Solution1: Two pointers

### Solution2: UsingMap

functwoSum(nums []int,targetint) []int {

numToIndex:=map[int]int{}

### Solution1: Two pointers

### Solution2: UsingMap

deftwo_sum(nums,target)

num_to_index= {}

##C

## Kotlin

## Swift

## Rust

1. 暴力解法的时间复杂度为`O(n^2)`，想提升效率，可以对数组进行排序，然后用双指针，一个指向数组头，一个指向数组尾，根据**和**情况决定`left += 1`还是`right -= 1`。

## Other languages

2. 找出了两个值后，需要用`index()`方法去找值对应的`index`。

- 时间复杂度：`O(N * log N)`。

- 空间复杂度：`O(N)`。

classSolution:

deftwoSum(self,nums: List[int],target:int) -> List[int]:

original_nums= nums.copy()

nums.sort()

left=0

right=len(nums)-1

while left< right:

sum_= nums[left]+ nums[right]

if sum_== target:

if sum_< target:

left+=1

right-=1

return [

original_nums.index(nums[left]),

len(nums)-1- original_nums[::-1].index(nums[right])

]

// Welcome to create a PR to complete the code of this language, thanks!