牛客题解-NC61两数之和

题目

给出一个整数数组,请在数组中找出两个加起来等于目标值的数,

你给出的函数twoSum 需要返回这两个数字的下标(index1,index2),需要满足 index1 小于index2.。注意:下标是从1开始的

假设给出的数组中只存在唯一解

例如:

给出的数组为 {20, 70, 110, 150},目标值为90 输出 index1=1, index2=2

输入:

1
[3,2,4],6

返回值:

1
[2,3]

思路

分析

题目提到只存在唯一解,故而考虑使用HashMap求解该问题。

对于每一个数,在存入HashMap之前先判断HashMap中当前是否存在可以和该数字相加为target的数字,有则返回。没有才将该数字和下标存入HashMap中。先判断后存入的方式能够避免使用到同一个数字。

要注意返回时下标需要+1.

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;


public class Solution {
/**
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
// write code here
int[] res = new int[2];
HashMap<Integer, Integer> map = new HashMap<>();
int len = numbers.length;
for(int i = 0; i<len; i++){
if(map.containsKey(target-numbers[i])){
res[0] = map.get(target-numbers[i])+1;
res[1] = i+1;
return res;
}
map.put(numbers[i],i);
}
return res;
}
}