LeetCode Algorithm 1. 两数之和10.31

56 阅读 0 评论 37 点赞

我是靠谱客的博主甜美寒风，最近开发中收集的这篇文章主要介绍LeetCode Algorithm 1. 两数之和10.31，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。
但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

输出示例

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

answer+分析

方法一：暴力枚举

①输入nums及target，nums按照逗号用split分割（注意输入的值是字符串类型）
②我的做法是定义一个函数来进行下标的寻找
③套用双层for循环，外层 i∈[ 0，len(nums)-1 ]，内层 j∈[ i+1,len(len(nums) ] （注意函数中nums应改为形参）
④ if 判断（注意将str类型转换为int类型）
⑤return [ i , j ] 根据题目要求返回相应格式的答案
⑥打印输出

nums = input("nums=").split(",")
target = int(input("target="))
def func(lis, goal):
for i in range(len(lis) - 1):
for j in range(i + 1, len(lis)):
if int(lis[i]) + int(lis[j]) == goal :
return [i, j]
res = func(nums, target)
print(res)

方法二：固定一个值，计算差值进行寻找（与法一类似）

①输入nums及target，nums按照逗号用split分割（注意输入的值是字符串类型）
②一个for循环，假设确定一个数nums[ i ]
③计算target与nums[ i ]的差值difference
④如果difference在nums列表中，则通过index找到该值的索引下标 j ，输出[ i ，j ]并break退出for循环
否则继续进行for循环

nums = input("nums=").split(",")
target = int(input("target="))
for i in range(len(nums) - 1):
difference = target - int(nums[i])
if str(difference) in nums:
j = nums.index(str(difference))
print([i, j])
break

法一和法二实质上是一种方法

方法三：使用dict/set类型，降低复杂度（由于哈希查找速度快）

# tip:dict/set 哈希
lis = input("nums=").split(",")
target = int(input("target="))
nums = {} # 定义一个字典
# 注意数据类型！！
for k, v in enumerate(lis):
# setdefault（键，值）用于设置值，键不存在 即 新增键值对，存在
即无效操作
nums.setdefault(int(v), str(k))
# get（键）用于获取值，键存在就获取值，不存在就返回None
t=nums.get(target - int(v))
if t:
print([k, int(t)])
break