Swift 两数之和 - LeetCode

题目:两数之和

描述:
给定一个整数数列,找出其中和为特定值的那两个数。

你可以假设每个输入都只会有一种答案,同样的元素不能被重用。

示例:

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

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

方法一:循环嵌套,时间复杂度O(n2),空间复杂度O(1)

代码如下:

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        let count = nums.count
        for i in 0..<count {
            for j in (i + 1)..<count {
                if nums[i] + nums[j] == target {
                    return [i,j]
                }
            }
        }
        return []
    }
}

执行时间:700ms。。。居然还战胜了75.28的Swift提交记录???

执行用时

方法二: 使用字典,时间复杂度O(n),空间复杂度O(n) 代码如下:

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        let count = nums.count
     
        var dic = [Int : Int]()
        
        for i in 0..<count {
            dic[nums[i]] = i
        }
        
        for i in 0..<count {
            let found = target - nums[i]
            if let j = dic[found], i != j {
                return [i, j]
            }
        }
        return []
    }
}

执行用时:24ms 用空间换时间,执行速度快了不少

执行用时

用Swift开始学习算法中,在LeetCode中开始做初级算法这一章节,将做的题目在此做个笔记吧。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1341 与3和5无关的数

1341 与3和5无关的数 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 白银 Silver 题目描述 Description ...

2864
来自专栏企鹅号快讯

1.12编程基础之函数与过程抽象/05:统计单词数

总时间限制: 1000ms 内存限制: 65536kB 描述 一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位置,有的还能统计出特定单...

27210
来自专栏数据结构与算法

P3809 【模版】后缀排序

题目背景 这是一道模版题。 题目描述 读入一个长度为 nn 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序从小到大排序,然后按顺序输...

2678
来自专栏JavaEdge

Java中类型参数“<T>”和无界通配符“<?>”的区别

List<T>最应该出现的地方,应该是定义一个泛型List容器 但List是库里自带的容器,看看ArrayList的源码头一行:

3051
来自专栏GreenLeaves

Oracle dbms_random随机函数包

dbms_random是oracle提供的一个随机函数包,以下是它的一些常用的功能: 1、dbms_random.value 作用:生成一个大于等于0,大于等于...

2135
来自专栏北京马哥教育

python3急速入门 (二) 列表的使用

云豆贴心提醒,这是马哥Linux运维Python3急速入门系列第1篇文章 列表用于组织其它数值,即写在方括号之间、用逗号分隔开的数值列表。列表内的项目不必全是...

2985
来自专栏微信公众号:Java团长

Java泛型详解

定义了一个List类型的集合,先向其中加入了两个字符串类型的值,随后加入一个Integer类型的值。这是完全允许的,因为此时list默认的类型为Object类型...

1092
来自专栏xingoo, 一个梦想做发明家的程序员

快速排序

算法思想:对于输入的子数组a[p:r],按下面三个步骤: 1 分解:以a[p]为基准元素将a[p:r]分成三段,a[p:q-1],a[q],a[q+1:r],使...

2109
来自专栏数据结构与算法

06:整数奇偶排序

06:整数奇偶排序 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给定10个整数的序列,要求对其重新排序。排序要求: 1...

3936
来自专栏猿人谷

成员以其在类中声明的顺序构造

分析以下代码的输出: #include<iostream> using namespace std; class A { public: A(int j):...

2006

扫码关注云+社区

领取腾讯云代金券