前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 001: Two Sum

Leetcode 001: Two Sum

作者头像
xuyaowen
发布2020-12-30 16:27:54
2270
发布2020-12-30 16:27:54
举报
文章被收录于专栏:XUYAOWEN的专栏XUYAOWEN的专栏

题目:

  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.

例子:

 [2,7,11,15], 9  输出 [0, 1]

思路:

  主要考虑:

    1、是否有重复得如 [3,2,4] 6 得情况,不要输出[0, 0] ,题目中说明:you may not use the same element twice.

    2、考虑不同方法主要有三种:暴力,两遍哈希表和一遍哈希表。

下面给出我的实现:

   两遍哈希表:

代码语言:javascript
复制
#coding:utf-8

'''
    leetcode 001 question
    author: xuyaowen time: 2018-04-02 
    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.
'''
class Solution(object):
    def twoSum(self, nums, target):
        pair = dict(zip(nums,range(len(nums))))
        for i in range(len(nums)):
            p =  target - nums[i]
            if  p in nums:
                if p == target/2 and pair[p] == i:
                    continue
                return [i, pair[p]] #所有的解对应当下的坐标
# 1319 ms 时间效率很慢
# 解决方法,两遍哈希表
ans =  Solution()
print(ans.twoSum([3, 3], 6))

  一遍哈希表:

代码语言:javascript
复制
#coding:utf-8

'''
    leetcode 001 question
    author: xuyaowen time: 2018-04-02 
    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.
'''
class Solution(object):
    def twoSum(self, nums, target):
        seen = {}
        for i, n in enumerate(nums):
            o = target-n
            if o in seen:
                return [seen[o], i]
            seen[n] = i
# 40ms
# 一遍哈希表
ans =  Solution()
print(ans.twoSum([2, 7, 11, 15], 9))

  暴力算法就不展示了。

     更多得代码请参见: https://github.com/yaowenxu/Leetcode

  转载请注明出处

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-04-03 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档