当前位置: 首页 > >

LeetCode-1 两数之和---Python代码实现及详解

发布时间:

题目:

? ? ? ? ?给定一个整数数组 nums?和一个目标值 target,请你在该数组中找出和为目标值的那?两个?整数,并返回他们的数组下标。


? ? ? ? ?你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。


?


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

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

思路:

? ? ? ? 首先要注意题目的要求读懂题意,不能重复使用相同元素,假如 target=4时不能重复使用2。数组中两个数相加等于目标值的只有一种答案。你可能会想到用到冒泡算法的思想。


方法一:使用冒泡冒泡算法思想+切片。(推荐)?index() 函数用于从列表中找出某个值第一个匹配项的索引位置。


? ? ? ? ? ? ? ? ? ?复杂度分析:时间复杂度:O(n)空间复杂度:O(1)


class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# 使用切片方法
for i in range(len(nums)):
if target-nums[i] in nums[i+1:]:
return [i, nums.index(target-nums[i], i+1)]

方法二:使用暴力解法


? ? ? ? ? ? ? ? ? ? ? ? ?复杂度分析:时间复杂度:O(n^2)空间复杂度:O(1)


class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""

# 使用暴力解法
length = len(nums)
for i in range(length):
for j in range(i+1, length):
if nums[i] + nums[j] == target:
return [i, j]

?


?


?



友情链接: