From LeetCode 1. Two Sum

Description

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.

Solution

First let’s talk about difference between list, set and map

  • list
    • If the number of elements in a list is small, it will waste a lot of memory space
  • set
    • Element in a set is just a key.
  • map
    • Map can use key to store number, and value to store index
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        records = dict()

        # 用枚举更方便，就不需要通过索引再去取当前位置的值
        for idx, val in enumerate(nums):
            if target - val not in records:
                records[val] = idx
            else:
                return [records[target - val], idx] # 如果存在就返回字典记录索引和当前索引