[编程题]two-sum
• 热度指数：36414 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
• 算法知识视频讲解

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

## 输入

`[3,2,4],6`

## 输出

```[2,3]
```
``````import java.util.HashMap;
public class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])){
return new int[]{map.get(nums[i])+1,i+1};
}
map.put(target - nums[i],i);
}
return null;
}
}
``````

```import java.util.HashMap;
public class Solution {
public int[] twoSum(int[] numbers, int target) {
int n = numbers.length;
int[] result = new int;
//map里面放 键为target-每个数的结果 值为下标
//每次放入的时候看是否包含 当前值
//有的话说明当前值和已包含的值下标的那个元素为需要的结果
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i=0;i<n;i++){
if(map.containsKey(numbers[i])){
result = map.get(numbers[i])+1;
result = i+1;
break;
}
else{
map.put(target - numbers[i], i);
}
}
return result;
}
}

class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
unordered_map<int, int> hashtable;
vector<int> result;
for(int i=0; i<numbers.size(); i++){
hashtable[numbers[i]] = i;
}
for(int i=0; i<numbers.size(); i++){
const int diff = target - numbers[i];
if(hashtable.find(diff) != hashtable.end() && hashtable[diff] > i){
result.push_back(i+1);
result.push_back(hashtable[diff]+1);
break;
}
}
return result;
}
};

Leetcode#1.Two Sum（两数之和）

``````package Array;
import java.util.Arrays;
import java.util.HashMap;
/**
* 1.Two Sum（两数之和）
* 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
* 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
*/
public class Solution1 {
public static void main(String[] args) {
Solution1 solution1 = new Solution1();
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = solution1.twoSum(nums, target);
System.out.println(Arrays.toString(result));
}
/**
* 用 HashMap 存储数组元素和索引的映射，在访问到 nums[i] 时，判断 HashMap 中是否存在 target - nums[i]
* 如果存在说明 target - nums[i] 所在的索引和 i 就是要找的两个数。
* 该方法的时间复杂度为 O(N)，空间复杂度为 O(N)，使用空间来换取时间。
*
* [@param nums
* @param target
* @return](/profile/547241) */
public int[] twoSum_2(int[] nums, int target) {
HashMap map = new HashMap();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[]{map.get(target - nums[i]) + 1, i + 1};
} else {
map.put(nums[i], i);
}
}
return null;
}
/**
* 暴力，时间复杂度为 O(N^2)
*
* [@param nums
* @param target
* @return](/profile/547241) */
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[i] + nums[j] == target) {
return new int[]{i + 1, j + 1};
}
}
}
return null;
}
}
``````

## 使用一个哈希表来解，第一遍扫描，保存到哈希表中，第二遍扫，看target-n在不在哈希表中，时间复杂度为O(n)。

``````class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
map<int, int> mapping;
vector<int> res;
for (int i = 0; i < numbers.size(); ++i) {
mapping[numbers[i]] = i;
}
for (int i = 0; i < numbers.size(); i++) {
int searched = target - numbers[i];
if (mapping.find(searched) != mapping.end() && i != mapping[searched]) {
res.push_back(i + 1);
res.push_back(mapping[searched] + 1);
break;
}
}
return res;
}
};
``````

//边建立hash表边查询。只用遍历到正确的答案就停止了。
//绝大部分情况下，时间和空间上都优于建立完整的hash表再查找匹配，只有最差情况下与之相同。
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> vec;
unordered_map<int, int> map;
for (int i = 0; i < numbers.size(); i++)
{
int len = target - numbers[i];
if (map.find(len) != map.end())
{
vec.push_back(map[len] + 1);
vec.push_back(i + 1);
break;
}
else
{
map[numbers[i]] = i;
}
}
return vec;
}
};

```class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
int n = numbers.size();
vector<int> result(2);
map<int,int> m;
for(int i=0;i<n;i++)
{
if(m.find(numbers[i]) != m.end())
{
result = (m[numbers[i]]);
result = (i+1);
break;
}else{
m[target-numbers[i]] = i+1;
}
}
return result;
}
};```

/**
*题目大意：在数组中找到两个值相加，与目标值相同，返回这两个值的索引，且索引一少于索引二。
*
*解题思路：
*1、双重遍历所有结果，显然效率低
*
*2、下面是第一次的错误想法，是无法判断数组中是否存在相同的元素
*采用hashMap存储数组，key-->数组val  ，val-->数组索引。
*遍历集合，target减去当前值，判断当前值是否存在于集合中，如果
*存在返回索引（hashMap采用hashcode（散列函数维护排序），为了快速查询而建立的），
*因此在这里利用hash算法中的快速查询，而且采用hashcode维护顺序，那么这个索引显然是有序的。无需比较。

*3、我们可以把每次相减后的结果和索引放到map集合中去，我们数组移动下一个数时，我们判断是否存在，如果存在，那么
*说明我们找到了这两个数。（这里的查找我们用的是hashcode（散列函数的快速查找））
*
*/
import java.util.*;
public class Solution {
public int[] twoSum(int[] numbers, int target) {
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();

int[] res=new int;
for(int i=0;i<numbers.length;i++){
if(map.get(numbers[i])!=null){
res=map.get(numbers[i]);
res=i+1;
}else{
int other =target-numbers[i];
map.put(other,i+1);
}

}
return res;
}
}

```class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
map<int, int> m;
vector<int> res;
for(int i=0; i<numbers.size(); i++){
m[numbers[i]] = i;
}
for(int i=0; i<numbers.size(); i++){
const int diff = target - numbers[i];
if(m.find(diff) != m.end() && m[diff] > i){
res.push_back(i+1);
res.push_back(m[diff]+1);
break;
}
}
return res;
}
};

```import java.util.*;
public class Solution {
/**
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
int[] result = new int;
HashMap<Integer, Integer> map = new HashMap<>();
/**
*每次存入的键是target-当前元素值，value存储的是循环遍历的下标值i
*/
for(int i = 0; i < numbers.length; i++){
if(map.containsKey(numbers[i])){
result = map.get(numbers[i]) + 1;
result = i + 1;
}else{
map.put(target - numbers[i], i);
}
}
return result;
}
}```

package com.company;

import java.util.HashMap;

/**
* @author 熟尔
* @createdate 2019/8/5 0005-13:21
* int[] a = {1,3,5,6,8,9};target = 12,找出数组中两个数字和为target的坐标并返回
*/

public class test01 {
public static void main(String[] args) {
int [] nembers = {2,6,3,7,11,15};
int target = 9;
// 复杂度 O(n*n),效率需要采用hashmap,
for (int i = 0; i < nembers.length; i++) {
for (int j = i+1; j <nembers.length  ; j++) {
int num= nembers[i]+nembers[j] ;
if (num == target)
{
i+=1;
j+=1;
System.out.println("index1 = "+i+"  index2 = "+j);
}

}
}

//使用hashmap

int[] arr = A123.B(nembers,target);
System.out.println("index1 = "+arr+"  index2 = "+arr);

}

}

class A123{
static int[] B(int[] a ,int n ){
HashMap<Integer, Integer> hashMap = new HashMap<>();
System.out.println(hashMap);
int[] sz = new int;
for (int i = 0; i < a.length; i++) {
System.out.println(i);
if(hashMap.containsKey(n-a[i])){
System.out.println("AAA检测下面的语句是否执行");
System.out.println(hashMap);
sz= hashMap.get(n-a[i])+1;

sz = i+1;
break;
}
System.out.println("检测下面的语句是否执行");
hashMap.put(a[i],i);

}
return  sz;
}
}
说点心里的话， 在纸上画画就出来了， 理解意思了， 你就知道原来就应该是这样。

```class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> res;
map<int,int> m;
for(int i = 0; i < numbers.size(); i ++ ){
if(m.count(numbers[i]) > 0){
res.push_back(m[numbers[i]] + 1);
res.push_back(i + 1);
break;
}
m[target - numbers[i]] = i;
}
return res;
}
};
```

```
vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> res;
map<int, int> m;
for (int i = 0; i < numbers.size(); ++i) {
int a = target - numbers[i];
if(m.find(a) == m.end())
//key到下标位置的map
m[numbers[i]] = i + 1;
else{
//找到了就把找到的下标放进去
res.push_back(m[a]);
//当前下标放进去
res.push_back(i + 1);
return res;
}
}
return res;
}

```

```//看大家都用的使先建立map，然后再找，其实可以边建立边找。
//代码如下。
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> ans(2,0);
map<int,int> arr;
for(int i = 0 ; i != numbers.size() ; ++i)
{
if(arr.find(target-numbers[i]) != arr.end())
{
int z = arr.find(target-numbers[i])->second;
z < (i+1) ? (ans = z ,ans = (i+1)):(ans = z        ,ans = i+1);
break;
}
else
arr.insert ( std::pair<int,int>(numbers[i],i+1) );
}
return ans;
}
};```

``` vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> res;
map<int,int> hash;
for(int i=0;i<numbers.size();i++){
if(hash.find(target-numbers[i])!=hash.end()){
res.push_back(hash[target-numbers[i]]+1);
res.push_back(i+1);
return res;
}
hash[numbers[i]]=i;
}
return res;
}
```

``````public int[] twoSum(int[] numbers, int target) {
int[] res = new int;
HashMap<Integer, Integer> hms = new HashMap<>();
for (int i = 0; i < numbers.length; i++) {
int val = numbers[i];
if(hms.containsKey(target - val)){
res = hms.get(target - val) + 1;
res = i + 1;
return res;
}else {
hms.put(val, i);
}
}
return res;
}
``````

Hi, this is my accepted JAVA solution. It only go through the list once. It's shorter and easier to understand. Hope this can help someone. Please tell me if you know how to make this better :)

```public int[] twoSum(int[] numbers, int target) { int[] result = new int;
Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < numbers.length; i++) { if (map.containsKey(target - numbers[i])) {
result = i + 1;
result = map.get(target - numbers[i]); return result;
} map.put(numbers[i], i + 1);
} return result;
}```

```//O(n)复杂度，遍历一遍，找到解就返回，没找到就放入map，key是值，value是下标加1；
public static int[] twoSum(int[] numbers, int target) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < numbers.length; i++) {
if(map.containsKey(target - numbers[i]))
return new int[]{map.get(target - numbers[i]), i+1};
map.put(numbers[i], i+1);
}
return null;
}```

```import java.util.HashMap;
public class Solution {
public int[] twoSum(int[] numbers, int target) {
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
int n = numbers.length;
int[] result = new int;
for(int i = 0; i < n; i++){
if(map.containsKey(target - numbers[i])){
//如果map里已经有所缺的另一个数字了 那就返回结果，如果没有，
//那就把本numbers[i], i 存入数组
result = map.get(target - numbers[i]) +  1;//target - numbers[i]是先放进map的
result = i + 1;//返回值下标从1开始
break;
}else{
map.put(numbers[i],i);
}
}
return result;
}
}```

```class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> res;
if (numbers.size() == 0)
return res;

map<int, int> finder;
int val;
for (int i = 0; i<numbers.size(); i++)
{
val = target - numbers.at(i);
finder.insert(pair<int, int>(val, i));
}

for (int i = 0; i<numbers.size(); i++)
{
int left = numbers.at(i);
if (finder.find(left) == finder.end())
continue;
else
{
if (finder[left] == i)
{
//cout << "test1" << endl;
//cout << i << endl;
continue;
}
else if (finder[left]<i)
{
//cout << "test2" << endl;
//cout << i << endl;
res.push_back(finder[left] + 1);
res.push_back(i + 1);
break;
}
}
}
//cout << "test3" << endl;
return res;
}
};```

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题