算法 Notes｜LeetCode 1. 两数之和 - easy

创创精灵 lv.1

发布时间：2022-11-14 20:56:17 339

1. 两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

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

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

暴力解 And 优化

第一时间想到使用双指针，依次遍历相加并判断是否等于 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
}

执行结果：

算法 Notes｜LeetCode 1. 两数之和 - easy_数组_02

个人简单分析下时间复杂度：

由于两层循环体，都是循环 nums 数组本身，也就是说时间复杂度为 O(n*n)，也就是 O()

第一次尝试分析，不对之处欢迎指点～

反思了下，可以直接在符合条件下直接 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
}

执行结果：

算法 Notes｜LeetCode 1. 两数之和 - easy_i++_04

再想想，似乎有些变量无需创建，直接 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)
}

执行结果：

算法 Notes｜LeetCode 1. 两数之和 - easy_leetcode_05

学习 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)
}

执行结果：

算法 Notes｜LeetCode 1. 两数之和 - easy_算法_06

有点尴尬，尝试了几次，还不如我最终的优化执行结果，不过也是一种方式。

学习 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()
}

执行结果：

算法 Notes｜LeetCode 1. 两数之和 - easy_i++_07