LeetCode 【1】 Two Sum --001
5月箴言
住进布达拉宫,我是雪域最大的王。流浪在拉萨街头,我是世间最美的情郎。—— 仓央嘉措
从本周起每周研究一个算法,并以swift实现之
001 -- Two Sum (两数之和)
题干英文版:
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
题干中文版:
给定一个整数数组 nums
和一个目标值 target
,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
目前想到两种解法:
方法一、暴力查询,两边for循环数组,计算是否存在等于目标值的,存在就返回对应的坐标,不存在 返回-1,-1
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
guard nums.count > 1 else{
return [-1,-1]
}
for i in 0..<nums.count-1{
var j = i+1
for j in j..<nums.count{
if(nums[i] + nums[j] == target){
return [i,j]
} }
}
return [-1,-1]
}
}
运行时间和所占内存:
Runtime: 472 ms, faster than 24.78% of Swift online submissions for Two Sum.
Memory Usage: 21 MB, less than 5.12% of Swift online submissions for Two Sum.
复杂度分析:
时间复杂度 O(n^2)。
方法二:利用字典,因为字典或者集合经常使用的原因是因为查询的时间复杂度是O(1),原因是一般字典和集合会要求他们的key都必须遵守Hashable协议
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
guard nums.count > 1 else{
return [-1,-1]
}
var dict:[Int:Int] = [:]
for i in 0..<nums.count {
let item = target-nums[i]
if let found = dict[item]{
return [found , i]
}else{
dict[(nums[i])] = i
}
}
return [-1, -1]
}
}
时间和空间复杂度:
Runtime: 48 ms, faster than 46.77% of Swift online submissions for Two Sum.
Memory Usage: 21.1 MB, less than 5.12% of Swift online submissions for Two Sum.
复杂度分析:
时间复杂度 O(n)。
可以看出方法二运行时间变为方法一的约1/10,空间复杂度区别不大。
关于时间复杂度和空间复杂度的概念,目前尚不是非常清晰(在之后会一步一步改进的)。
167 -- Two Sum II - Input array is sorted
题干英文版:
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.
Note:
- Your returned answers (both index1 and index2) are not zero-based.
- You may assume that each input would have exactly one solution and you may not use the same element twice.
Example:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
题干中文版:
给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
说明:
- 返回的下标值(index1 和 index2)不是从零开始的。
- 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。
目前想到的实现思路是根据001的两数之和,可知加入到字典中的数据的索引是从小到大的,因此我们可以知道的是字典中已经存在的索引应该是小于后来遍历到的,
因此其实现如下:
class Solution {
func twoSum(_ numbers: [Int], _ target: Int) -> [Int] { guard numbers.count > 1 else{
return []
}
//因为先加到字典中的肯定是数组靠前的下标
var dict:[Int:Int] = [:]
for i in 0..<numbers.count {
let item = target-numbers[i]
if let found = dict[item]{
return [found + 1,i + 1]
}else{
dict[(numbers[i])] = i
}
}
return []
}
}
运行时间和内存
Runtime: 28 ms, faster than 100.00% of Swift online submissions for Two Sum II - Input array is sorted.
Memory Usage: 21.1 MB, less than 5.09% of Swift online submissions for Two Sum II - Input array is sorted.
关于算法的实现目前的思路:
1、先实现,用现在经常使用到的数据结构去实现,复杂什么也没关系,最关键是实现它
2、考虑耗时,内存消耗
不要忘了安全校验:诸如判空,特殊处理等。
下期code
有缘看到的亲们:文中若有不对之处,还请劳驾之处,谢谢!
最新文章
- 【原】Android热更新开源项目Tinker源码解析系列之三:so热更新
- SynchronousQueue应用
- javascript操作cookies
- 《Java7中 下划线的新特性》
- tomcat+apache 实现负载均衡之一:同一台电脑部署2个以上tomcat
- (JAVA)从零开始之--对象输入输出流ObjectInputStream、ObjectOutputStream(对象序列化与反序列化)
- iOS 画音频波形曲线 根据音频数据版
- JS day01——window对象、执行顺序、线程模型
- Notepad++ 7.3.2 Download 64-bit x64 / 32-bit x86
- IPhone开发“此证书是由未知颁发机构签名”解决办法
- doT.js——前端javascript模板引擎问题备忘录
- leetcode算法: Find the Difference
- Dubbo序列化多个CopyOnWriteArrayList对象变成同一对象的一个大坑!!
- Oracle 查询结果集行数分析
- 洛谷P2764 最小路径覆盖问题
- 2018 Multi-University Training Contest 2 部分简单题解析
- SQL中on条件与where条件的区别
- python接口自动化测试十二:对返回的json的简单操作
- Orangegreenworks封装rpgmakermv
- and与or的用法
热门文章
- osg define shape(create box)
- List根据多个字段分组
- 123457123456#0#-----com.threeapp.ErTongPaint01-----儿童宝宝绘画涂鸦游戏02
- 微信支付 composer 方法 --- 实测有效
- hadoop:/bin/bash: /bin/java: No such file or directory
- 树莓派连接显示器后设置ssh服务开机自动开启
- sqlserver 数据库操作导出数据sql工具
- NET CORE与Spring Boot
- Java面试 - 重载(Overload)和重写(Override)的区别?
- Java面试 - 什么是单例设计模式,为什么要使用单例设计模式,如何实现单例设计模式(饿汉式和懒汉式)?