专栏首页Rust语言学习交流一起学Rust-实战leetcode(一)

一起学Rust-实战leetcode(一)

第二期:一起学Rust-变量及类型

第一期:一起学Rust-环境安装

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/two-sum

这是来源于leetcode的一道题,我们使用Rust来实现。

先理清思路,首先根据题目,不使用重复元素,假设只存在一个正确答案,最简单直接的思路,就是两层循环,逐个相加判断是否等于target的值,如果相等,则返回相应的索引数字。

可以看出这个算法的时间复杂度是O(nlogn),这个就不在这里进行实现了,现在直接考虑一下是否能够优化。

考虑上面的实现,要想优化,就只能考虑O(n)复杂度了,那么就需要去掉一层循环。

将目的抽象化就是“x + y = target”,求x和y的索引,可以看做就是求x和y,目前是通过两个数字相加再与目标比较的方法,这样就需要循环出x和y的值,那么我们反过来考虑,y = target - x 通过减法来消除一个未知变量,而这个y一定是x遍历过的值或还未遍历到的。所以需要将x遍历过的值进行保存,很容易可以想到读写时间复杂度最低的就是HashMap,不过HashMap的get方法返回值是一个之前没有提到过的枚举 Option<T>类型,这个类型有两个枚举值Some(T)和None,当get的内容不存在时会返回None,存在数据时则会将值放在Some内一起返回:Some(value),这样就可以通过match匹配得出。

下面贴出代码:

use std::collections::HashMap;

fn main(){
    let nums = vec![2, 7, 11, 15];
    let n = two_sum(nums, 9);

    println!("{:?}", n);   //结果会获取到0,1
}
fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut res:Vec<i32> = vec![];  //定义可变向量
    let mut h: HashMap<i32, i32> = HashMap::new();  //定义可变hashmap
    for (k, n) in nums.iter().enumerate() {
        let key = target - n;  //取差值
        match h.get(&key) {    //判断差值是否存在
            Some(v) => {
                //如果差值存在,则吧结果由小到大的放入向量中,
                res.push(*v);
                res.push(k as i32);
                break;
            },
            None => {
                //差值不存在则将当前值和索引存入hashmap
                h.insert(*n, k as i32);
            }
        }
    }
    res
}

练习相关的代码:https://github.com/a74946443/learn_rust

本文分享自微信公众号 - Rust语言学习交流(rust-china)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-18

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 微服务设计指南

    微服务是当今软件工程师的一个热门话题。让我们了解如何使用微服务架构风格构建真正模块化、业务敏捷的IT系统。

    纯洁的微笑
  • 微信小程序获取用户所在城市

    在微信小程序中, 获取用户的地理位置是需要权限的, 如果只是获取用户所在的城市信息, 那只需查看用户ip所在的城市就好了, 下面我们就完成获取用户ip的小程序逻...

    Javanx
  • 为什么ConcurrentHashMap的读操作不需要加锁?

    ConcurrentHashmap(1.8)这个并发集合框架是线程安全的,当你看到源码的get操作时,会发现get操作全程是没有加任何锁的,这也是这篇博文讨论的...

    用户5224393
  • Django-pure-pagination的使用

    Django自带有分页的两个类,但是用起来没有第三方这个分页模块方便,下面介绍一下django-pure-pagination使用方法。该库基于django.c...

    菲宇
  • 利用Python完成对王者荣耀英雄全皮肤的下载

    本文使用python的第三方模块requests爬取王者荣耀所有英雄的图片,并将图片按每个英雄为一个目录存入文件夹中,方便用作桌面壁纸。

    python学习教程
  • JavaScript定时器与执行机制详细介绍

    由于JS是单线程,所以同一时间只能执行一个任务,其他任务就得排队,后续任务必须等到前一个任务结束才能开始执行。

    Javanx
  • Nginx缓存原理及机制

    上篇文章介绍了Nginx一个较为重要的知识点:Nginx实现接口限流。本篇文章将介绍Nginx另一个重要知识点:Nginx缓存原理。其实说到缓存技术大家应该...

    逆月翎
  • 说说HttpClient三种Http Basic Authentication认证方式

    HTTP 提供一个用于权限控制和认证的通用框架。最常用的 HTTP 认证方案是 HTTP Basic authentication。Http Basic 认证是...

    黄泽杰
  • Nginx日志配置

    众所周知,线上如果出现事故我们通常都是查看日志去进行问题定位并且进行修复。使用好Nginx日志有利于我们线上进行修复异常问题。在Nginx中日志主要分为两种:...

    逆月翎
  • MongoDB使用小结:一些常用操作分享

    本文整理了一年多以来我常用的MongoDB操作,涉及mongo-shell、pymongo,既有运维层面也有应用层面,内容有浅有深,这也就是我从零到熟练的历程。

    拓荒者

扫码关注云+社区

领取腾讯云代金券