01. 两数之和-Swift leetcode每日一题

/**
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
*/

//方案1 时间复杂度O(n*n)，空间复杂度O(n)
class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var endArr = [Int]()
        print(nums)
        for i in 0..<nums.count {
            for j in (i+1)..<nums.count {
                if (nums[i] + nums[j]) == target {
                    endArr.append(i)
                    endArr.append(j)
                }
            }
        }
        return endArr
    }
}

let s1 = Solution()
let arrY = s1.twoSum([2, 7, 11, 15], 9)

方案二： 使用字典，时间复杂度O(n)，空间复杂度O(n)

class Solution2 {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var arr = [Int]()
        var dict = [Int:Int]()
        for i in 0..<nums.count {
            dict[nums[i]] = i
        }
        
        for i in 0..<nums.count {
            let found = target - nums[i]
            if let j = dict[found], i != j {
                if !arr.contains(i) {
                    arr.append(i)
                    arr.append(j)
                }
            }
        }
        return arr
    }
}
let s2 = Solution2()
let arr2 = s2.twoSum([2, 7, 11, 15], 9)