TwoSum

 1 """复杂度O(n)"""
 2 class Solution:
 3     def twoSum(self, nums, target):
 4         dict1={}
 5         for i in range(len(nums)):
 6             if nums[i] in dict1: #利用字典查找复杂度为O(1),而暴力解法问题就在每次比较复杂
度依然为o(n)
 7                  return [dict1[nums[i]],i] #return满足刷题要求
 8             else:
 9                 dict1[target-nums[i]] = i   #字典的赋值，dict[key]=valuw
10 if __name__ =="__main__":
11     s=Solution()
12     s.twoSum([2,7,11,15],9)
13 """双指针"""
14 class Solution:
15     def twoSum(self,nums,target):
16         l=len(nums)
17         array = list(zip(nums,range(l)))   #zip将两个列表按对应元素形成含多个元组的新列表
18         array.sort()    #此时array已经改变了，但是内存位置也变了
19         low=0
20         high=l-1
21         while low<high:
22             S=array[low][0]+array[high][0]
23             if S<target:
24                 low += 1
25             elif S>target:
26                 high -= 1
27             else:
28                 return [array[low][1],array[high][1]]