Swift开发

LeetCode Problem 1 Two-Sum Swift语言

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

  • 2个for循环能解决问题,但是复杂度O(n^2),肯定会超时
  • 无序搜索肯定会想到HashTable,不过这题不仅要求定性yes/no,还要求原数组中的index,那就只能把index也放进去了。
class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var dict:[Int:Int] = [:]
        for (index1, item) in nums.enumerated() {
            if let index2 = dict[target - item] {
                return [index2, index1]
            }
            dict[item] = index1
        }
        return []
    }
}

复杂度方面这里是极限了,具体到Swift,可以再努力让代码优雅些。
jietu20180902-213607
Xcode 10开始会直接支持数组中查找元素的index,代码又可以少几行。

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        for (index1, item) in nums.enumerated() {
            if let index2 = nums.firstIndex(of: target - item) {
                return [index1, index2]
            }
        }
        return []
    }
}