首页 > 试题广场 >

两数之和

[编程题]两数之和
  • 热度指数:401387 时间限制: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     
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;
    }
};

发表于 2019-05-05 10:22:12 回复(0)
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[2];
        for(int i = 0; i < n; i++){
            if(map.containsKey(target - numbers[i])){
                //如果map里已经有所缺的另一个数字了 那就返回结果,如果没有,
                //那就把本numbers[i], i 存入数组
                result[0] = map.get(target - numbers[i]) +  1;//target - numbers[i]是先放进map的
                result[1] = i + 1;//返回值下标从1开始
                break;
            }else{
                map.put(numbers[i],i);
            }
        }
        return result;
    }
}

编辑于 2016-06-23 22:00:38 回复(3)
import java.util.*;


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

发表于 2020-11-18 11:36:30 回复(0)
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 回复(15)
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)
可以利用哈希表来存放两数之差来对数字进行对比。
  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)
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++ 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 回复(4)
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)
用一个哈希表,存储每个数对应的小标,复杂度为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)
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)
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)
牛客的数组为啥是从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)
哈希表遍历实现
发表于 2014-09-18 16:29:47 回复(0)
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)

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)
看了下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)
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)
两个相加不好都存到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)
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)