LeetCode-Two Sum

目录隐藏

问题

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

Example 1:

Input:

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

Output:

 [0,1]

Output:

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

Example 2:

Input:

 nums = [3,2,4], target = 6

Output:

 [1,2]

Example 3:

Input:

 nums = [3,3], target = 6

Output:

 [0,1]

Constraints:

2 <= nums.length <= 10³
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists.

解答：

创建一个字典，以值为key，value为值具体的索引信息，因为exactly one solution ，所以可以不考虑等值的情况，遍历列表判断，target-当前值，是否存在字典中。也就是判断当前值与之前所有值（存放在字典中）是否满足和为指定值target的。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
      dict = {}     
      for index, value in enumerate(nums):
        remaining = target-value
        if remaining in dict:
          return [dict[remaining], index]
        dict[value] = index
      return []

时间复杂度O(n), 遍历列表时间为n，查询字典时间复杂度O(1)

空间复杂度O(n), 最坏的情况下需要在字典中存放所有的数值。

参考及引用

https://leetcode.com/problems/two-sum/solution/

Photo by Frank Cone from Pexels

LeetCode-Two Sum

问题

解答：

参考及引用

garlic