首页 > 试题广场 >

两数之和

[编程题]两数之和

热度指数：401663 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。

（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

数据范围： $2\leq len(numbers) \leq 10^5$ ， $-10 \leq numbers_i \leq 10^9$ ， $0 \leq target \leq 10^9$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(nlogn)$

示例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

算法知识视频讲解

查看答案及解析

Python3

AntonHan

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @param target int整型 
# @return int整型一维数组
#
class Solution:
    def twoSum(self , numbers: List[int], target: int) -> List[int]:
        d = {}
        for i in range(len(numbers)):
            m = numbers[i]
            if target - m in d:
                return (d[target - m] + 1, i + 1)
            d[m] = i

发表于 2024-02-07 19:59:31 回复(0)

Python3

Francisco909

#Python3
class Solution:
    def twoSum(self , numbers: List[int], target: int) -> List[int]:
        # write code here
        dd = {}
        ll = len(numbers)
        for i in range(ll):
            if target - numbers[i] in dd:
                return [dd[target - numbers[i]]+1, i+1]
            dd[numbers[i]] = i
#总用时161ms

发表于 2023-12-12 16:04:09 回复(0)

Python3

LeoAlan

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        dict = {}
        for i in range(len(numbers)):
            if target - numbers[i] in dict:
                return [dict[target - numbers[i]] + 1, i + 1]
            else:
                dict[numbers[i]] = i

发表于 2023-09-14 22:07:47 回复(1)

Python3

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)

Python3

有担当的柠檬精拒绝内卷

class Solution:
    def twoSum(self , numbers: List[int], target: int) -> List[int]:
        tmp_dict={}
        for i in range(len(numbers)):
            if target - numbers[i] in tmp_dict.keys():
                return [tmp_dict[target - numbers[i]]+1,i+1]
            tmp_dict[numbers[i]]=i

发表于 2023-08-01 23:34:07 回复(0)

Python3

EdwinPang

class Solution:

def twoSum(self, numbers: List[int], target: int) -> List[int]:

# refactor and sort the list

sorted_numbers = [(idx, val) for idx, val in enumerate(numbers)]

sorted_numbers.sort(key=lambda x: x[1])

# find the cutpoint

s = 0

idx_1, idx_2 = 0, 1

for i in range(len(sorted_numbers) - 1):

s = sorted_numbers[i][1] + sorted_numbers[i + 1][1]

if s >= target:

idx_1, idx_2 = i, i + 1

break

# search bi-directional

while True:

s = sorted_numbers[idx_1][1] + sorted_numbers[idx_2][1]

if s == target:

break

elif s > target:

idx_1 -= 1

else:

idx_2 += 1

# return the result

res = [sorted_numbers[idx_1][0] + 1, sorted_numbers[idx_2][0] + 1]

res.sort()

return res

发表于 2023-06-23 12:03:36 回复(0)

Python3

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)

Python3

牛客824096536号

class Solution:

def twoSum(self, numbers: List[int], target: int) -> List[int]:

hashmap = {}

for i, num in enumerate(numbers):

hashmap[num] = i + 1

for i, num in enumerate(numbers):

complement = target - num

if complement in hashmap and hashmap[complement] != i + 1:

return [

min(i + 1, hashmap[complement]),

max(i + 1, hashmap[complement]),

]

发表于 2023-03-24 13:45:12 回复(0)

Python3

Media_Luhn

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 创建哈希表,用于保存值、下标键值对
        hash = dict()
        # 在哈希表中查找target-numbers[i]
        for i in range(len(numbers)):
            temp = target - numbers[i]
            if temp not in hash:
                hash[numbers[i]] = i
            else:
                return [hash[temp]+1,i+1]

发表于 2023-03-07 15:46:33 回复(0)

Python3

Namely

时间复杂度O(n)，空间复杂度O(n)

class Solution:
    def twoSum(self , numbers: List[int], target: int) -> List[int]:
        s = {}
        for index, item in enumerate(numbers):
            if item in s:
                return [s[item]+1,index+1]
            else:
                s[target - item] = index

发表于 2023-03-01 18:01:34 回复(1)

Python3

SZ有钱人

提示运行超时了，有大佬帮忙优化一下吗？python3的，我的思路是从numbers数组中最后一个数开始依次进行两个数字的求和，直到第二个数和第一个数相加，还是说这题嵌套循环就是会超时？

def twoSum(self , numbers: List[int], target: int) -> List[int]:
        # write code here
        k=[]
        for j in range(len(numbers)):
            for i in range(len(numbers)-1):
                a=numbers[len(numbers)-1-j]+numbers[len(numbers)-1-j-i-1]
                k.append(a)
                if target in k:
                    b=len(numbers)-1-j+1
                    c=len(numbers)-1-j-i
                    d=[c,b]
                    return d

发表于 2023-02-02 21:20:20 回复(0)

Python3

ajaxx

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

# @param numbers int整型一维数组

# @param target int整型

# @return int整型一维数组

class Solution:

def twoSum(self , numbers: List[int], target: int) -> List[int]:

# write code here

help = {}

res = []

for i in range(len(numbers)):

if (target - numbers[i]) in help.keys():

return sorted([i+1, help[target-numbers[i]]+1])

else:

help[numbers[i]] = i

return res

发表于 2022-12-30 16:25:02 回复(0)

Python3

dadadadad

将数组排序后进行计算，当计算结果大于target进行剪枝

class Solution:

def twoSum(self , numbers: List[int], target: int) -> List[int]:

# write code here

sNum = []

for tmp in numbers:

sNum.append(tmp)

sNum.sort()

for i in range(len(sNum)-1):

for j in range(i+1, len(sNum)):

if sNum[i]+sNum[j] == target:

pos1 = numbers.index(sNum[i])

if sNum[i]!=sNum[j]:

pos2 = numbers.index(sNum[j])

return [min(pos1, pos2)+1, max(pos1, pos2)+1]

else:

pos2 = numbers[i+1:].index(sNum[j]) + i+1

return [pos1+1, pos2+1]

elif sNum[i]+sNum[j] > target:

break

发表于 2022-11-13 13:04:47 回复(0)

Python3

牛客401957887号

class Solution:
    def twoSum(self , numbers: List[int], target: int) -> List[int]:
        # write code here
        temp_dict = {}
        for index, item in enumerate(numbers):
            if len(temp_dict) != 0:
                if (target-item) in temp_dict.keys():
                    return sorted([index+1, temp_dict.get(target-item)+1])
            temp_dict[item] = index

发表于 2022-10-23 19:33:38 回复(0)

Python3

牛客357651024号

class Solution:
    def twoSum(self , numbers: List[int], target: int) -> List[int]:
        # write code here
        if 2 <= len(numbers) <= 10 ** 5:
            for i in range(len(numbers)):
                for j in range(i+1,len(numbers)):
                    if -10 <= int(numbers[i]) <= 10 ** 9 and 0 <= target <= 10 ** 9:
                        s = int(numbers[i]) + int(numbers[j])
                        if int(numbers[i]) + int(numbers[j]) == target:
                            return ([i+1 , j+1])
不知道什么原因就是不正确

发表于 2022-07-22 23:23:04 回复(3)