Leetcode Solutions(一) two-sum

题目

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

Example

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

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

解题思路

Go

a + b = target

也可以看成是

a = target - b

在map[整数]整数的序号中,可以查询到a的序号。这样就不用嵌套两个for循环了。

func twoSum(nums []int, target int) []int {
    m := make(map[int]int, len(nums))
    for i, b := range nums {
        if j, ok := m[target-b]; ok {
            return []int{j, i}
        }
        m[nums[i]] = i
    }
    return nil
}

Python

  1. 由于要找到符合题意的数组元素的下标,所以先要将原来的数组深拷贝一份,然后排序。
  2. 然后在排序后的数组中找两个数使它们相加为target。这个思路比较明显:使用两个指针,一个指向头,一个指向尾,两个指针向中间移动并检查两个指针指向的数的和是否为target。如果找到了这两个数,再将这两个数在原数组中的位置找出来就可以了。
  3. 要注意的一点是:在原来数组中找下标时,需要一个从头找,一个从尾找,要不无法通过。如这个例子:numbers=[0,1,2,0]; target=0。如果都从头开始找,就会有问题。
class Solution:
    def twoSum(self, nums, target):
        if len(nums) <= 1:
            return False
        d = dict()
        for i in range(len(nums)):
            if nums[i] in d:
                return [d[nums[i]], i]
            else:
                d[target - nums[i]] = i

恩,最后找队友一起刷题。喜欢可以联系我

原文发布于微信公众号 - Python爬虫与算法进阶(zhangslob)

原文发表时间:2018-05-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专注研发

希尔排序(shell‘ sort)

希尔排序是1959 年由D.L.Shell 提出来的,相对直接排序有较大的改进。希尔排序又叫缩小增量排序

1003
来自专栏云霄雨霁

排序----插入排序

1430
来自专栏C语言及其他语言

【蓝桥杯系列】第一节 C的基本用法

置顶编程范收获更多热门编程快讯 大家好,最近很多小伙伴向我反应小编!我参加了蓝桥杯但是我连那是什么都不知道,我该怎么训练?是不是在网站刷题就可以啊? 在这里我要...

3887
来自专栏PHP在线

PHP面试题,PHP笔试题

题目一: <?php echo -10%3; ?> 答案:-1。 考查:优先级。 因为-的优先级比%求余的优先级低, 也就是-(10%3)。 题目二: prin...

91115
来自专栏智能算法

Python学习(四)---- 列表生成式、生成器、迭代器和内置函数

https://blog.csdn.net/fgf00/article/details/52061971

902
来自专栏Python攻城狮

数据结构与算法 - 排序与搜索排序与搜索

冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重...

1003
来自专栏机器学习实践二三事

Numpy使用3

上一篇博客介绍了numpy的几种初始化方式和numpy的数据类型(dtype)和shape的相关知识,这篇介绍numpy矩阵的索引与切片 矢量化 numpy数组...

1888
来自专栏老司机的技术博客

人人都能学会的python编程教程6:列表(list)

当索引超出了范围时,Python会报一个IndexError错误,所以,要确保索引不要越界,记得最后一个元素的索引是len(classmates) - 1。如果...

42710
来自专栏从流域到海域

《笨办法学Python》 第4课手记

《笨办法学Python》 第4课手记 这节课目的是让你掌握变量,跟C语言非常类似,很简单。 左边是变量名用”=”号给变量赋值。 不同的是我没有看到变量声明,作者...

1838
来自专栏老司机的技术博客

宝宝都能学会的python编程教程6:列表(list)

上期编程题的答案如上图。 列表(list) list是一种有序的集合,可以随时添加和删除其中的元素。 当索引超出了范围时,Python会报一个IndexErr...

3566

扫码关注云+社区

领取腾讯云代金券