Daily LeetCode 1. Two Sum

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

Easy

今天开始刷一波LeetCode上的Top 100 Liked Questions

问题描述

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].

思路及代码：

暴力解法：

感觉一般easy难度的题目都能用暴力求解，用一个二重循环，对list进行两次遍历，判断当前元素与后来某一个元素和是否为target

代码：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for index, num in enumerate(nums):
            for j in range(index + 1, len(nums)):
                if nums[j] == target - num:
                    return [index, j]

字典：

通过字典在遍历过程中保存[num, index]对，在后续的遍历中，检查target-num是否存在于字典中，若存在，即这两个元素和为target，返回两个index即可，若不存在，则将当前元素以及index加入到字典中。

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