Leetcode1——两数之和

题目

在给定的数组中，找出两个数相加之和等于目标数target，返回两个数的下标index1,index2

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Python代码

# 暴力求解：两层for循环，最容易实现

class Solution:
    def twoSum(self, List, target):
        n = len(List)
        for i in range(n):
            # 注意：数据不能重复，下标i前面的数据不能再次使用
            for j in range(i+1, n):
                if List[i] + List[j] == target:
                    return i,j
        
twosum = Solution()
twosum.twoSum([2, 7, 11, 15], 9)

# 一层for循环，另一个if语句通过减法实现，和暴力破解比较类似

class Solution:
    def twoSum(self, List, target):
        n = len(List)
        for i in range(n):
            if target - List[i] in List:
                return [i, List.index(target-List[i])]
            else:
                continue

twosum = Solution()
twosum.twoSum([2, 7, 11, 15], 9)

优化方式

• 巧妙利用enumerate函数

class Solution(object):
    def twoSum(self, nums, target):
        d = {}
        for i, num in enumerate(nums):  # enumerate函数同时返回：索引和列表中的值
            if target - num in d:
                return [d[target - num], i]  # 如果另一个元素在字典中，返回的是另一个元素的值value，也就是索引，同时还有i
            else:
                d[num] = i   #  若不在字典中，则主动往字典中添加元素，k-v满足"num":i，此时字典中的值就是索引
                # print(d)

        
twosum = Solution()
print(twosum.twoSum([2, 11, 7, 15], 9))

# 通过字典形式
class Solution:
    def twoSum(self, List, target):
        dic = {}  # 定义空字典
        for i in range(len(List)):  # 遍历长度
            if List[i] not in dic:
                dic[target - List[i]] = i + 1  
            else:
                return dic[List[i]] - 1, i

        return -1, -1
    
twosum = Solution()
twosum.twoSum([2, 11, 7, 15], 9)