LeetCode 1. 两数之和 - Easy
LeetCode 1. 两数之和 - Easy
贺biubiu
发布于 2020-12-14 11:06:50
发布于 2020-12-14 11:06:50
推荐点击查看原文，体验更佳～
1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]暴力解、优化
第一时间想到使用双指针，依次遍历相加并判断是否等于 target。
代码如下：
fun twoSum(nums: IntArray, target: Int): IntArray {
if (nums.isEmpty()) {
return IntArray(0)
}
var resultArray = IntArray(2)
var isl = false
var i = 0
var j = 1
while (i < nums.size - 1){
while (j < nums.size){
if (nums[i] + nums[j] == target) {
resultArray[0] = i
resultArray[1] = j
isl = true
break
}
j++
}
if (isl) {
break
}
i++
j = i + 1
}
return resultArray
}执行结果：
个人简单分析下时间复杂度：
- 由于两层循环体，都是循环 nums 数组本身，也就是说时间复杂度为 O(n*n)
第一次尝试分析，不对之处欢迎指点～
反思了下，可以直接在符合条件下直接 return，修改后代码如下：
fun twoSum(nums: IntArray, target: Int): IntArray {
if (nums.isEmpty()) {
return IntArray(0)
}
var resultArray = IntArray(2)
var i = 0
var j = 1
while (i < nums.size - 1){
while (j < nums.size){
if (nums[i] + nums[j] == target) {
resultArray[0] = i
resultArray[1] = j
return resultArray
}
j++
}
i++
j = i + 1
}
return resultArray
}执行结果：
再想想，似乎有些变量无需创建，直接 return 多好？
fun twoSum(nums: IntArray, target: Int): IntArray {
if (nums.isEmpty()) {
return intArrayOf(0,0)
}
var i = 0
var j = 1
while (i < nums.size - 1){
while (j < nums.size){
if (nums[i] + nums[j] == target) {
return intArrayOf(i,j)
}
j++
}
i++
j = i + 1
}
return intArrayOf(0,0)
}执行结果：
学习 LeetCode 执行用时最短事例
fun twoSum(nums: IntArray, target: Int): IntArray {
if (nums.isEmpty()) {
return intArrayOf(0, 0)
}
for (i in nums.indices) {
for (j in 0..i) {
if (i == j) {
continue
}
val a = nums[i];
val b = nums[j];
if (a + b == target) {
return intArrayOf(j, i)
}
}
}
return intArrayOf(0, 0)
}执行结果：
有点尴尬，尝试了几次，还不如我最终的优化执行结果，不过也是一种方式。
学习 LeetCode 执行消耗内存范例
使用 HashMap 方式确实没有想到，不过思路还是蛮不错的，个人简要分析一波：
- 首要的基础校验必不可少，依次循环输入 nums 数组也是正常思路；
- 设置临时 map，用于存储当前 nums 当前不符合的数字，顺便依次将相减结果去 map 中判断是否存在，不存在继续将此值添加 map，否和情况下直接获取当前结果对应索引以及当前循环 map 索引 return 即可。
有关详情，查阅代码：
fun twoSum(nums: IntArray, target: Int): IntArray {
if (nums.isEmpty()) {
return intArrayOf(0, 0)
}
val map: MutableMap<Int, Int> = HashMap()
for (i in nums.indices) {
val complement = target - nums[i]
if (map.containsKey(complement)) {
return intArrayOf(map[complement]!!, i)
}
map[nums[i]] = i
}
throw Exception()
}执行结果：
题外话
没明白为啥执行 LeetCode 几次结果不是 100%，不过也没关系，比较学习算法最终目的并不是求最优解，而是通过一次次的分析、优化，让个人思维进行一个提升。个人感觉是这样的。
自己摸索，查看范例。一起努力，加油～
Thanks
- LeetCode
- 冰与火之歌：「时间」与「空间」复杂度
- MathJax basic tutorial and quick reference
LeetCode 历史文章
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-11-30，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读