专栏首页HLQ_StruggleLeetCode 1. 两数之和 - Easy

LeetCode 1. 两数之和 - Easy

第107次推文

推荐点击查看原文,体验更佳~

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 历史文章

本文分享自微信公众号 - 贺利权(hlq_struggle),作者:贺利权

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

原始发表时间:2020-11-30

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode-easy-array-两数之和

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

    shengjk1
  • LeetCode-1 两数之和

    给定一个整数数组 nums和一个目标值 target,请你在该数组中找出和为目标值的那 两个整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个...

    用户3470542
  • 【LeetCode】1.两数之和

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

    Delevin
  • LeetCode | 1.两数之和

    上面的题就是 两数之和 题目的截图,同时 LeetCode 会根据选择的语言给出了一个类的定义或者函数的定义,然后在其中实现 两数之和 的解题过...

    码农UP2U
  • leetcode:1 两数之和

    贵哥的编程之路
  • leetcode-1-两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案...

    Spaceack
  • leetcode 1. 两数之和

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

    火与剑
  • Leetcode 1:两数之和

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

    py3study
  • leetcode(1)---两数之和

    gzq大数据
  • LeetCode-1 两数之和(python3)

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

    dreamkong
  • LeetCode 1. 两数之和(swift)

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

    freesan44
  • leetcode No 1. 两数之和

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

    week
  • Leetcode#1.Two Sum(两数之和)

    题目描述 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。 示例: 给定 nums ...

    武培轩
  • LeetCode 1:两数之和 Two Sum

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

    爱写bug
  • Leetcode 1. 两数之和 (Python版)

    有粉丝说我一个学算法的不去做Leetcode是不是浪费,于是今天闲来没事想尝试一下Leetcode,结果果断翻车,第一题没看懂,一直当我看到所有答案的开头都一样...

    风骨散人Chiam
  • LeetCode-1-Two Sum | 两数之和

    简单题。常规解法(解法1),用两个for循环来做,第一个循环从数组nums下标为0开始遍历,第二个循环从数组下标1开始遍历,如果没找到两数之和的target值,...

    Zoctopus
  • LeetCode 1. 两数之和(哈希)

    题目链接:https://leetcode-cn.com/problems/two-sum/

    Michael阿明
  • Leetcode|1. 两数之和(哈希表)

    SL_World
  • LeetCode 1. 两数之和【新方式】

    https://leetcode-cn.com/problems/two-sum/

    freesan44

扫码关注云+社区

领取腾讯云代金券