首页 > 试题广场 > two-sum
[编程题]two-sum
  • 热度指数:36414 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给出一个整数数组,请在数组中找出两个加起来等于目标值的数,
你给出的函数twoSum 需要返回这两个数字的下标(index1,index2),需要满足 index1 小于index2.。注意:下标是从1开始的
假设给出的数组中只存在唯一解
例如:

给出的数组为 {2, 7, 11, 15},目标值为9
输出 ndex1=1, index2=2



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


示例1

输入

[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;
    }
}
发表于 2018-05-11 21:05:18 回复(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 回复(5)
用一个哈希表,存储每个数对应的小标,复杂度为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 回复(1)

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++ 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 回复(1)
//边建立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;
    }
};
发表于 2019-02-18 16:17:50 回复(0)
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[0] = (m[numbers[i]]);
        		result[1] = (i+1);
        		break;
			}else{
				m[target-numbers[i]] = i+1;
			}
		}
		return result;
    }
};

发表于 2017-09-07 00:38:34 回复(0)
/**
*题目大意:在数组中找到两个值相加,与目标值相同,返回这两个值的索引,且索引一少于索引二。
*
*解题思路:
*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[2];
        for(int i=0;i<numbers.length;i++){
         if(map.get(numbers[i])!=null){
             res[0]=map.get(numbers[i]);
             res[1]=i+1;
         }else{
             int other =target-numbers[i];
             map.put(other,i+1);
         }
            
            
        }
        return res;
    }
}
发表于 2016-09-12 12:13:54 回复(0)
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)
大家都写的比较好,分享一下,涨涨经验。首先肯定是可以使用两层for循环进行实现的,运行也能通过,只是复杂度稍微高一点点。也可以用HashMap的特性来进行求解,其实就是map的key存储target-当前循环的值,value存储当前循环的下标i,就可以实现了。当然使用HashMap会占用一些内存空间,这应该也是空间换时间的一种体现吧。
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[2];
        HashMap<Integer, Integer> map = new HashMap<>();
        /**
        *每次存入的键是target-当前元素值,value存储的是循环遍历的下标值i
        */
        for(int i = 0; i < numbers.length; i++){
            if(map.containsKey(numbers[i])){
                result[0] = map.get(numbers[i]) + 1;
                result[1] = i + 1;
            }else{
                map.put(target - numbers[i], i);
            }
        }
        return result;
    }
}
编辑于 2020-06-10 14:44:52 回复(0)
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[0]+"  index2 = "+arr[1]);

    }


}

  class A123{
 static int[] B(int[] a ,int n ){
        HashMap<Integer, Integer> hashMap = new HashMap<>();
     System.out.println(hashMap);
        int[] sz = new int[2];
        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[0]= hashMap.get(n-a[i])+1;

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

        }
        return  sz;
    }
}
 说点心里的话, 在纸上画画就出来了, 理解意思了, 你就知道原来就应该是这样。 
发表于 2019-08-05 16:30:50 回复(0)
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)

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; }


编辑于 2019-05-05 19:39:59 回复(0)
//看大家都用的使先建立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[0] = z ,ans[1] = (i+1)):(ans[1] = z        ,ans[0] = i+1);               
                 break;
            }
            else
                arr.insert ( std::pair<int,int>(numbers[i],i+1) );
        }
        return ans;
    }
};

编辑于 2018-03-11 16:04:11 回复(0)
 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;
    }

发表于 2017-11-07 10:10:06 回复(0)
public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        HashMap<Integer, Integer> hms = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            int val = numbers[i];
            if(hms.containsKey(target - val)){
                res[0] = hms.get(target - val) + 1;
                res[1] = i + 1;
                return res;
            }else {
                hms.put(val, i);
            }
        }
        return res;
    }
发表于 2017-06-25 20:56:04 回复(1)

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[2];
    Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < numbers.length; i++) { if (map.containsKey(target - numbers[i])) {
            result[1] = i + 1;
            result[0] = map.get(target - numbers[i]); return result;
        } map.put(numbers[i], i + 1);
    } return result;
}
发表于 2017-03-13 00:42:56 回复(0)
//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;
	 }

发表于 2016-10-18 11:11:52 回复(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)
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;
}
};

发表于 2016-03-24 20:58:32 回复(0)