首页 > 试题广场 >

两数之和

[编程题]两数之和
  • 热度指数：412821 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

数据范围：，，
要求：空间复杂度 ，时间复杂度
示例1

输入

[3,2,4],6

输出

[2,3]

说明

因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回[2,3]
示例2

输入

[20,70,110,150],90

输出

[1,2]

说明

20+70=90
算法知识视频讲解
添加回答
liononon头像 liononon 
import java.util.HashMap;
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        int[] result = new int[2];
        //map里面放 键为target-每个数的结果 值为下标 
        //每次放入的时候看是否包含 当前值 
        //有的话说明当前值和已包含的值下标的那个元素为需要的结果
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0;i<n;i++){
            if(map.containsKey(numbers[i])){
                result[0] = map.get(numbers[i])+1;
                result[1] = i+1;
                break;
            }
            else{
                map.put(target - numbers[i], i);
            }
        }
        return result;
    }
}

此题和leetcode上有所不同，leetcode上下标已改为从0开始

发表于 2016-05-17 19:44:31 回复(16)
Python3
刺猬她很瘦头像 刺猬她很瘦
class Solution:
    def twoSum(self , numbers , target ):
        # write code here
        for i in range(len(numbers)-1,0,-1) :
            sub = target - numbers[i]
            if sub in numbers and numbers.index(sub) != i :
                List = [numbers.index(sub)+1,i+1]
                return List
发表于 2021-08-21 23:06:16 回复(2)
JavaScript Node
周欣仪头像 周欣仪
可以利用哈希表来存放两数之差来对数字进行对比。
  1. 定义一个哈希表
  2. 用目标数字减去数字中的数字得到差，去哈希表中查看，是否存在差，如果不存在，则将数组中的数字存放入哈希表
  3. 如果哈希表中存在差，则取出数字的下标。
例如题目中的[3,2,4]  6 执行步骤如下所示：
  1. 6-3=3  哈希表中没有数字3，则将3存入哈希表
  2. 6-2=4 哈希表中没有4，则将2存入哈希表，index为2
  3. 6-4=2 正好哈希表中有数字2，则从哈希表中获得数字2的下标2，和4在数组中的下标+1为3
  4. 因此返回2和3
正式的代码如下所示： 
function twoSum( numbers ,  target ) {
    // write code here
    //定义一个hash表用来存放数据
    var map=new Map()
    //获取数组的长度
     var len=numbers.length
     //遍历数组
     for(var i=0;i<len;i++)
         {
             //将目标数字减去数组中数字，得到差
            var num=target-numbers[i]
            //如果哈希表中没有这个差，将这个数字放进去
            if(!map.has(num))
                {
                    map.set(numbers[i],i+1)
                }
             else{
                 //如果有差，则获取到数字的下标
                 return [map.get(num),i+1]
             }
         }

}



发表于 2021-08-17 17:17:59 回复(2)
shijiacheng头像 shijiacheng 
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;
    }
}
发表于 2018-05-11 21:05:18 回复(0)
C/C++
华科平凡头像 华科平凡

C++ solution

使用一个哈希表来解，第一遍扫描，保存到哈希表中，第二遍扫，看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;
    }
};
发表于 2017-10-31 15:10:22 回复(5)
JavaScript Node
skrheart头像 skrheart
牛客的数组为啥是从1开始😥 
/**
  * 
  * @param numbers int整型一维数组 
  * @param target int整型 
  * @return int整型一维数组
  */
function twoSum( numbers ,  target ) {
    const map = new Map()
    for(let i = 0;i < numbers.length;i++){
        if(map.get(target - numbers[i]) !== undefined){
            return [map.get(target - numbers[i])+1,i+1]
        }
        map.set(numbers[i],i)
    }
}
module.exports = {
    twoSum : twoSum
};

发表于 2021-10-31 00:15:24 回复(0)
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
class Solution {
public:
  /**
   * 
   * @param numbers int整型vector 
   * @param target int整型 
   * @return int整型vector
   */
  vector<int> twoSum(vector<int>& numbers, int target) {
    unordered_map<int, int> m;
    for (int i = 0; i < numbers.size(); ++i) {
      if (m.find(target - numbers[i]) != m.end())
        return {m[target - numbers[i]], i + 1};
      m[numbers[i]] = i + 1;
    }
    return {-1, -1};
  }
};

发表于 2021-07-11 16:20:50 回复(3)
BrainerGao头像 BrainerGao
用一个哈希表，存储每个数对应的小标，复杂度为O(n)
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;
    }
};
发表于 2016-06-27 21:51:22 回复(7)
Python3
聪明的猴子深藏功与名头像 聪明的猴子深藏功与名 
class Solution:
    def twoSum(self , numbers: List[int], target: int) -> List[int]:
        # write code here
        tm= {}
        res = []
        for i, v in enumerate(numbers):
            if v in tm:
                res.append(tm[v]+1)
                res.append(i+1)
            else:
                tm[target - v] = i
        return res


发表于 2022-04-27 14:53:07 回复(2)
C
牛客313433821号头像 牛客313433821号 
int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) {
    // write code here
    int *result = malloc(8);
    *returnSize = 2;
    for(int i = 0; i < numbersLen; i++)
    {
        // 过滤本身已经超过target的值，可以节省很多时间
        if(numbers[i]>target)
            continue;
        for(int j = i+1;j < numbersLen; j++)
            if(numbers[i]+numbers[j] == target)
            {
                *result = i+1;
                *(result+1) = j+1;
                return result;
            }
    }
    return NULL;
}
没有过滤时间那一步，答案过不了。
发表于 2022-01-26 10:32:12 回复(5)
有问题找社区小助手头像 有问题找社区小助手
哈希表遍历实现
发表于 2014-09-18 16:29:47 回复(0)
C
Thruth头像 Thruth
看了下c语言的题解，本来想找一个c语言使用散列表法的来解决的方案，但是最终没找到。
于是自己还是老实地使用传统的散列表法来解决，并给出一个c语言的散列表法以作参考。 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param numbers int整型一维数组 
 * @param numbersLen int numbers数组长度
 * @param target int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
//使用拉链法解决冲突
typedef struct HashMapNode{
    int data;
    struct HashMapNode* next;
}HashMapNode,*HashMapHead;
//这个函数用于给散列表添加元素
void addHashMapNode(HashMapHead* head,int index){
    HashMapHead a = (HashMapHead)malloc(sizeof(HashMapNode));
    a->data=index;
    a->next=NULL;
    if(*head==NULL){
        *head=a;
    }
    else{
        HashMapHead temp = *head;
        HashMapHead b;
        while(temp!=NULL){
            b=temp;
            temp=temp->next;
        }
        a->next=b->next;
        b->next=a;
    }
}
int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) {
    // write code here
    int* result = (int*)malloc(2*sizeof(int));
    *returnSize+=2;

    //创建一个散列表，大小：50000（主要是想尽量减少冲突的同时，又少用些内存）
    int hashMapLen = 50000;
    HashMapHead hash[hashMapLen];
    //初始化散列表(这一步是挺浪费时间的，但是我真不知道怎么在c语言里初始化一个指针数组为null)
    for(int j=0;j<hashMapLen;j++){
        hash[j]=NULL;
    }

    //work
    for(int i=0;i<numbersLen;i++){
        //注意，求余在计算机语言中是可以出现负数的，因此要进行绝对值处理
        int index=abs((numbers[i])%hashMapLen);
        //下面逻辑思路与官方思路相同
        if(hash[index]!=NULL){
            HashMapHead temp = hash[index];
            while(temp!=NULL){
                if(numbers[temp->data]+numbers[i]==target){
                    result[0] = temp->data+1;
                    result[1] = i+1;
                    return result;
                }
                temp=temp->next;
            }
            int newIndex=abs((target-numbers[i])%hashMapLen);
            addHashMapNode(&hash[newIndex],i);
        }
        else {
            int newIndex=abs((target-numbers[i])%hashMapLen);
            addHashMapNode(&hash[newIndex],i);
        }
    }
    return result;
}
此处给出该方法的效率，并与官方的散列表法作比较，以校验性能没问题。
最终这个解法与官方的c++性能差不多。

最后提一嘴，在c语言的题解中，我发现有很多优化后的双循环能做到更快的速度，不过我想这与测试集的数据有很大关联。不管如何，从理论上来说，即便是优化后的双循环，时间复杂度也还是O(n2)，而散列表法，在无冲突的条件下，理论上时间复杂度为O(n)
发表于 2023-02-16 17:40:32 回复(0)
Python
LHC0512头像 LHC0512
Python 
class Solution:
    def twoSum(self, numbers, target):
        map1 = {}
        for i in range(len(numbers)):
            if target - numbers[i] in map1:
                return [map1[target - numbers[i]] + 1, i + 1]
            else:
                map1[numbers[i]] = i


发表于 2021-02-22 22:22:01 回复(3)
Java
武培轩头像 武培轩

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;
    }
}
编辑于 2018-04-17 23:50:31 回复(0)
Java
tornado123头像 tornado123 
import java.util.*;
public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        int len = numbers.length;
        int[] result = new int[2];
        for(int i = 0; i < len; i++) {
            for(int j = i+1; j < len; j++) {
                if(numbers[i] + numbers[j] == target) {
                    result[0] = i + 1;
                    result[1] = j + 1;
                }
            }
        }
        return result;
    }
}

发表于 2020-11-26 10:51:38 回复(12)
Java
BlueProtocol头像 BlueProtocol
两个相加不好都存到Map里面去，那么就使用减法来解决问题！！！ 
public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        // write code here
		Map<Integer,Integer> map = new HashMap<>();
		for (int i = 0; i < numbers.length; i++) {
			if (map.containsKey(target - numbers[i])) {
				return new int[]{map.get(target - numbers[i])+1,i +1};
			}else {
				map.put(numbers[i],i);
			}
		}
		return null;
    }
}


发表于 2023-03-18 22:31:25 回复(1)
anas头像 anas 
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;
    }
};

使用一个map保存每一个不同的数字最后出现的坐标，然后从下标0处开始进行查找。
即使有重复的数字，由于map中保存的是最后一次出现的位置，那样即使由两个相同
的值构成的数对也可以被找到。m[diff] > i，这个条件使用的比较好。

发表于 2016-07-17 11:54:06 回复(0)
Python3
zackw头像 zackw 
# 用例全部通过版本：
class Solution:
    def twoSum(self , numbers: List[int], target: int) -> List[int]:
        # write code here
        for i in range(len(numbers) - 1):
            if numbers[i] <= target: # 用于降低时间复杂度
                for j in range(i+1, len(numbers)):
                    if numbers[i] + numbers[j] == target:
                        return [i+1, j+1]
        return []

发表于 2023-09-09 20:32:17 回复(0)
C++
ZZZ2021头像 ZZZ2021 
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        unordered_map<int, int> hash;
        hash[numbers[0]]=1;
        for(int i=2;i<=numbers.size();++i){
            if(hash.count(target-numbers[i-1])){
                return {hash[target-numbers[i-1]], i};
            }
            else {
                hash[numbers[i-1]]=i;
            }
        }
        return {};
    }
};

发表于 2023-07-10 21:33:55 回复(1)
Python3
pzq头像 pzq 
 # 方法一：哈希表
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        ## 哈希表，用字典实现(python的字典即用哈希表实现)
        tab_hash = {}
        res = []
        for ind, val in enumerate(numbers):
            # 计算差值
            val2 = target - val
            # 在哈希表（即字典中）中查找差值
            ind2 = tab_hash.get(val2)
            # 判断所需差值是否存在
            if ind2 is not None:  # 存在，返回结果
                res = [ind + 1, ind2 + 1]
                res.sort()
                break
            else:  # 不存在，保存当前结果到哈希表中
                tab_hash[val] = ind
        return res


# 方法二： 双指针
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 写入索引
        data = [(val, ind) for ind, val in enumerate(numbers)]
        # 排序
        data.sort(key=lambda x: x[0])
        # 由于有序, 用双指针从前后同时查找
        ind1, ind2 = 0, len(data) - 1
        while True:
            # 终止条件(题目可知，一定可以找到)
            if data[ind1][0] + data[ind2][0] == target:
                break
            # 当前值较小，增大左边的索引
            if data[ind1][0] + data[ind2][0] < target:
                ind1 += 1
            # 当前值较大，减小右边的索引
            if data[ind1][0] + data[ind2][0] > target:
                ind2 -= 1
        res = [data[ind1][1] + 1, data[ind2][1] + 1]  # 题目中要求的数组下标从1开始算起
        res.sort()  # 保证从小到大
        return res

发表于 2023-05-17 00:18:51 回复(0)
提交观点

问题信息

数组 哈希
难度：
573条回答 82137浏览

热门推荐

通过挑战的用户

查看代码

相关试题

两数之和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号