leetcode with python:1. Two Sum

从今天起在此纪录用python写leetcode的心路历程
希望能以一天两三题的速率下去更新
让自己的程式更加精进

题目:

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.

简单来说就是题目给定一个目标值(target)和一个list,而我们找出list中两个相加等于target的数的index,再以阵列型态回传

一开始看到这题我的想法相当直观:

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

直接暴力遍历寻找相加等于target的两个值,想当然耳,最后速度只有5776ms(faster than 13.38%)(没超时就该偷笑了)

于是我找了一下更快的写法,在讨论区发现了叫hash map的方法
研究过后程式变这样

class Solution:    def twoSum(self, nums: List[int], target: int) -> List[int]:        m={}        for i,n in enumerate(nums):            d=target-n            if d in m:                return [m[d],i]            m[n]=i

先建立一个dictionary,用以纪录 value:index 的hash map
从第一项开始,透过target减去当下值寻找对应值是否在hash map内
若无则在hash map 写入 当下值:当下index,再跑下一项
直到在hash map找到对应值的存在,就将对应值index取出和当下index一同return

透过边遍历检索边建立hash map大幅加快了程式的运行,複杂度由O(n^2)降到O(n),运行速度也增为52ms (faster than 99.64%)
同时在研究过程中学到hash(杂凑)的概念

本题学习到的重点:杂凑(hash)
那我们下题见