你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

【leecode】第一题:两数之和

2021/11/8 5:18:01

今天开始,每天一道LeetCode题,不得不说第一道题就见证了自己的基本功有多薄弱


题目:

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

注意:数组中同一个元素不能在答案里重复出现(允许数组中有相同的数,但位置不同)


解题思路:

初级:for循环找配对

高级:考虑哈希索引、时间复杂度(多次循环会占用大量的时间)


刚开始自己看题敲的代码

count = []
for i,j in nums,nums:
    while i - j != 0:
        if i + j == v:
            count.append(nums.index(i))
            count.append(nums.index(j))
            print(count.sort())
            break
        else:
            continue
count = []
for i in nums:
    for j in nums:
        if i != j:
            if i+ j == target:
                count.append(nums.index(i),nums.index(j))
                print(count)
                break
            else:
                continue
        else:
            continue

果然,对索引和流程语法的不熟悉,不懂得如何用代码表达自己的想法

最后,还是百度查找别人的答案进行理解


别人写的代码

自己参考借鉴了一下(意思就是能理解,不会敲)

要掌握的知识点:字典的添加用法、流程的循环方式、列表元素的索引

# 网上代码,自己修改了一下
class Solution:
    def twosum(self,nums,target):           # 传入参数
        d = {}                              # 用字典来配对
        for i in range(len(nums)):          # 循环遍历nums元素
            x = target - nums[i]            # 因为target = x + i
            if nums[i] in d:                # 假如i在字典里面
                return d[nums[i]],i         # 返回字典中x的值和i
            else:
                d[x] = i                    # 可以理解成d[target - i] = i

可以自己带入nums = [2,7,11,15]尝试一下去理解代码

代码逻辑:

  • x = target - y        因为x + y = target
  • 把每次x的结果都装进字典里面,也就是字典的key,再把value等于i
  • 然后继续循环把nums中的 i 拿去跟字典的x匹配,记住x其实就是target-i,
  • 如果发现nums中的 i 在字典里面,也就是说字典里面存在一个元素,这个元素满足target-i
  • 那么就返回字典中的这个元素 d[nums[i]] 和 i

记住:第一次循环 if 时,必定先走else,因为字典里一开始是没有元素的,也就是nums[i]  not in d

这时,字典就会把这个 i 的对应值(target - i)存进字典里面,然后才是正常的循环


代码测试速度

参考链接:1.两数之和-Python-LeetCode_linfeng886的博客-CSDN博客_两数之和python 


官方代码

(原理其实是一样的)

# 官方代码
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

测试速度

 参考链接:力扣


有兴趣的大佬可以尝试继续优化代码,追求执行用时到最低.....