美文网首页
leetcode 001 两数之和

leetcode 001 两数之和

作者: 搜捕儿 | 来源:发表于2020-04-11 22:28 被阅读0次

两数之和

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

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

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

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

解答:

第一次提交: 超时了...


681586607307_.pic_hd.jpg

正确解答:

// method 1 : 执行用时56ms
func twoSum(_ nums : [Int] , _ target : Int) -> [Int] {
    
    //var dict = Dictionary<Int,Int>()
    var dic = [Int:Int]()
    var i = 0
    for n in nums { //遍历数组将每一项数组值作为key,对应的数组下标作为value添加到字典里
        dic[n] = i
        i += 1
    }
    
    var result = [-1, -1]
    var j = 0
    for n in nums { //遍历数组,直接在上述字典中依次查找key为(target - n)的value,找到此value且与j值不同,即为答案
        if dic.keys.contains(target - n) && j != dic[target - n] {
            result[0] = j
            result[1] = dic[target - n] ?? -1
        }
        j = j + 1
    }
    
    return result
}

let arr = [2, 7, 11, 8]
let result_arr = twoSum(arr, 18)
print(result_arr)

// method 2 : 执行用时616ms
func twoSum2(nums : [Int], target : Int) -> [Int] {
    
    for i in 0..<nums.count-1 {
        let nn = nums[i]
        for j in i+1..<nums.count {
            let mm = nums[j]
            if nn + mm == target
            {
                return [i,j]
            }
        }
    }
    return [-1,-1]
}

let arr2 = [2, 7, 11, 8]
let result_arr2 = twoSum2(nums: arr2, target: 15)
print(result_arr2)

// method 3 : 耗时同方法一,但是消耗内存更小一些
func twoSum3 (nums : [Int], target : Int) -> [Int] {
    
    var dict : [Int : Int] = [:]
    for (index, value) in nums.enumerated() {
        if let dValue = dict[target - value] {
            return [dValue, index]
        }
        dict[value] = index
    }
    
    return []
    
}

let arr3 = [2, 7, 11, 8]
let result_arr3 = twoSum3(nums: arr2, target: 15)
print(result_arr3)

关于for-in

Swift取消了OC中的C形式的for循环。只用一种单一的for - in形式来取代

其中关于下标的获取方式

方式一: 通过enumerate来获取

let testArr = [9,7,3,8,5,2,1,0,6]
for num in testArr {
    print(num)
}

for num in testArr.enumerated() {
    print(num.element,num.offset)
}

方式二: 使用元组来方便获取元素索引

for (n, c) in "Swift".characters.enumerated() {
           print("\(n): '\(c)'")
       }
    ///     // Prints "0: 'S'"
    ///     // Prints "1: 'w'"
    ///     // Prints "2: 'i'"
    ///     // Prints "3: 'f'"
    ///     // Prints "4: 't'"

相关文章

  • leetcode 001 两数之和

    两数之和 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并...

  • LeetCode实战001 两数之和

    原题链接 题目描述 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个...

  • [leetcode]001.两数之和

    题目 官网连接给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数...

  • leetcode001-两数之和

    问题描述 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并...

  • leetcode-001-两数之和

    题目内容 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 ...

  • 【LeetCode通关全记录】1. 两数之和

    【LeetCode通关全记录】1. 两数之和 题目地址:1. 两数之和[https://leetcode-cn.c...

  • 双指针

    两数之和 click here for leetcode detail[https://leetcode-cn.c...

  • LeetCode刷题001:两数之和

    前言 为了养成做笔记的习惯,决定将自己的积累的点点滴滴都做记录。一直觉得自己在算法这块很欠缺,今天在闲暇之余,刷了...

  • leetcode经典解析——001两数之和

    地址:https://leetcode-cn.com/problems/two-sum/ 1. 题目与解析 若用两...

  • 【leetcode系列】001-两数之和

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

网友评论

      本文标题:leetcode 001 两数之和

      本文链接:https://www.haomeiwen.com/subject/gxnpmhtx.html