【Leetcode-python】1.Two Sum

题目：给定一个整数数组，返回两个数字的索引，使它们相加到特定目标。假设每个输入只有一个解决方案，并且不会两次使用相同的元素。

例：给定nums = [2,7,11,15]，target = 9， 因为nums [ 0 ] + nums [ 1 ] = 2 + 7 = 9， 返回[ 0，1 ]。

解法：

一、暴力方法，时间复杂度是O(n^2)

使用两次嵌套循环

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
result=[]
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i]+nums[j]==target:
result.append(i)
result.append(j)
return result

二、字典方法（哈希思想），时间复杂度是O(n)

先把数组存储在字典里，再检查字典中是否存在target-nums[i]，同时考虑target-nums[i]和num[i]不应该是数组中同一位置元素，即满足题目中的要求：不会两次使用相同的元素。题中说明每个输入只有一个解决方案，即每个target等于数组两个固定位置的元素相加和，但是我们需要考虑到两个位置的元素值可能存在相等的情况。

代码思路：遍历一次数组，找到每个位置元素nums[i]对应的target-nums[i]的差值。如果差值存在字典里，就取出差值对应的索引，返回这个差值索引和当前位置元素nums[i]的索引i。如果差值不存在，就把当前位置元素nums[i]作为key,i作为value存入字典。

由于target等于数组两个固定位置（一个较小位置，一个较大位置）的元素相加和，代码方法遍历到较小位置元素，其对应差值一定不存在字典中，此时将这个较小位置元素值和索引存入字典，当遍历到较大位置元素时，其对应的差值就是之前已经存入字典的较小位置元素，即可返回结果。

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dic={}#字典
for i in range(len(nums)):
diff=target-nums[i]
if diff in dic:
return [dic[diff],i]
else:
dic[nums[i]]=i

最后

以上就是痴情冬瓜为你收集整理的【Leetcode-python】1.Two Sum的全部内容，希望文章能够帮你解决【Leetcode-python】1.Two Sum所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。