NC61 两数之和

解法一：哈希表

通过样例 10/12

class Solution:
    def twoSum(self , numbers , target ):
        # write code here
        # 可以用哈希表的方法解决
        dic = {}
        
        for i in range(len(numbers)):
            dic[numbers[i]] = i
        
        element1 = 0
        element2 = 0
        for key in dic:
            find = target - key
            if find in dic and dic[key] != dic[find]:
                
                element1 = dic[key]
                element2 = dic[find]
                break
        if element1 > element2
            return [element2+1, element1+1]
        return [element1+1, element2+1]

分析：遇到不同下标但是数字相同时的情况，就很难解决了

image.png

哈希表的正确解法：边遍历边判断

遍历数组-》判断 target - numbers[i] 是否在 map 里 -> 是的话，直接返回出来 =》否的话，把 number[i] 当作key把i当作value放进map

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

解法二：排序+对撞指针（done）

#
# 
# @param numbers int整型一维数组 
# @param target int整型 
# @return int整型一维数组
#
class Solution:
    def twoSum(self , numbers , target ):
        # write code here
        # 排序
        numbersBak = numbers.copy()
        numbersBak.sort()
        print(numbersBak)
        
        # 对撞指针
        left = 0
        right = len(numbersBak) - 1
        
        while left < right:
            total = numbersBak[left] + numbersBak[right]
            
            if total < target:
                left += 1
            elif total > target:
                right -= 1
            elif total == target:
                break
        
        num1 = numbersBak[left]
        num2 = numbersBak[right]

        
        # 查找在原数组的下标
        retList = []
        for i in range(len(numbers)):
            if len(retList) == 2:
                break
            if numbers[i] == num1 or numbers[i] == num2:
                retList.append(i)
        retList = [e+1 for e in retList]
        retList.sort()
        return retList

image.png