力扣算法练习BM50—两数之和

题目

给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

数据范围：2≤len(numbers)≤105，10≤numbersi​≤109，0≤target≤109

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

示例1

输入：[3,2,4],6

返回值：[2,3]

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

解题思路

方法一：直接两个for循环遍历列表，找到相加等于target的元素下标，返回下标时需加一

方法二：遍历列表，若target减去遍历当前值再直接去找哈希表中是否有key，若有则返回排序后的下标并加一，若无则把上一个元素添加到哈希表中，再继续遍历列表

题解

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @param target int整型 
# @return int整型一维数组
#
class Solution:
    def twoSum(self , numbers: List[int], target: int) -> List[int]:
    # 1.暴力法--超时
       l=len(numbers)
       result=[]
       for i in range(l):
        for j in range(i,l):
            if i==j:continue
            if numbers[i]+numbers[j]==target:
                result.append(i+1)
                result.append(j+1)
                return result
    # 2.哈希表--key-value的方式，target减去遍历当前值再直接去找是否有key，若有则返回排序后的下标，若无则遍历下一个key
        l=len(numbers)
        hash={}
        for i in range(l):
            if target-numbers[i] not in hash.keys():
                hash[numbers[i]]=i
            else:
                return [hash[target-numbers[i]]+1,i+1]