LeetCode 1. Two Sum

栏目: 编程工具 · 发布时间: 6年前

内容简介:Given an array of integers, returnYou may assume that each input would have给定一个整数数组和一个目标值,找出数组中和为目标值的
  • 英文

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.

  • 中文

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

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

示例

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

题解

  • 题解 1

两层循环暴力求解,对于列表的每个数,依次使其与其后所有的数单独求和,判断和是否为目标值。

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        length = len(nums)
        for i in range(length - 1):
            for j in range(i + 1, length):  # i 之后的数
                if nums[i] + nums[j] == target:  # 判断是否等于目标值
                    return i, j
  • 题解 2

用一层循环,直接在里面查询 target-nums[i] 是否存在于 nums 列表中,速度比题解 1 快了许多。

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            x = target - nums[i]
            if x in nums:  # 是否有对应的数与 nums[i] 的和为目标值
                j = nums.index(x)
                if i == j:
                    continue
                else:
                    return i, j  # 输出结果
  • 题解 3

遍历数组,然后使用字典,键为 target-nums[i] ,值为 i ,依次判断 nums[i] 是否已经在字典中,如果是,则输出结果,即和为目标值的两个数。否则把 target-nums[i] 的值存入字典。

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = {}
        for i in range(len(nums)):
            x = target - nums[i]
            if nums[i] in d:  # 判断是否已经在字典中
                return d[nums[i]], i  # 输出结果
            else:
                d[x] = i  # 存入字典

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

C语言接口与实现

C语言接口与实现

David R. Hanson / 郭旭 / 人民邮电出版社 / 2011-9 / 75.00元

《C语言接口与实现:创建可重用软件的技术》概念清晰、实例详尽,是一本有关设计、实现和有效使用C语言库函数,掌握创建可重用C语言软件模块技术的参考指南。书中提供了大量实例,重在阐述如何用一种与语言无关的方法将接口设计实现独立出来,从而用一种基于接口的设计途径创建可重用的API。 《C语言接口与实现:创建可重用软件的技术》是所有C语言程序员不可多得的好书,也是所有希望掌握可重用软件模块技术的人员......一起来看看 《C语言接口与实现》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

html转js在线工具
html转js在线工具

html转js在线工具