两数之和
算法知识视频讲解
时间限制：2秒 空间限制：64M
知识点
数组
哈希
题目
题解(43)
讨论(308)
排行
描述
给出一个整数数组，请在数组中找出两个加起来等于目标值的数，
你给出的函数twoSum 需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2.。注意：下标是从1开始的
假设给出的数组中只存在唯一解
例如：
给出的数组为 {20, 70, 110, 150},目标值为90
输出 index1=1, index2=2

示例1
输入：
[3,2,4],6
复制
返回值：
[2,3]
复制
说明：
因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以输出[2,3]
关联企业
关联职位
相似企业真题

思路和心得

1.哈希字典统计即可
类似dp “往前探”的思想
2.从前往后，每到一处，查找前面有没有能与自己配对成功的
哈希字典加速了这一查找过程

python3代码

#
# 
# @param numbers int整型一维数组 
# @param target int整型 
# @return int整型一维数组
#
class Solution:
    def twoSum(self , numbers , target ):
        # write code here
        val_idx = dict()
        for i, x in enumerate(numbers):
            y = target - x
            if y in val_idx:
                return [val_idx[y], i + 1]
            val_idx[x] = i + 1

c++代码

class Solution {
public:
    /**
     * 
     * @param numbers int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
    vector twoSum(vector& numbers, int target) 
    {
        // write code here
        unordered_map val_idx;
        int n = numbers.size();
        for (int i = 0; i < n; i ++)
        {
            int x = numbers[i];
            int y = target - x;
            if (val_idx.count(y) > 0)
                return vector{val_idx[y], i + 1};
            val_idx[x] = i + 1;
        }
        return vector{};
    }
};