LeetCode – 1. Two Sum

題目連結: https://leetcode.com/problems/two-sum/

參考解法: https://leetcode.com/problems/two-sum/discuss/1629845/Solution-Swift%3A-Two-Sum-(%2B-test-cases)

法ㄧ(Brute force) Time complexity: O(n^2)

    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        for i in 0 ..< (nums.count - 1) {
        	for j in (i + 1) ..< nums.count {
        		if nums[i] + nums[j] == target {
        			return [i, j]
        		}
        	}
        }
        return []
    }

法二(Dynamic programming) Time complexity: O(n)

    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    	var dic: [Int: Int] = [:]
    	for (index, item) in nums.enumerated() {
    		if let val = dic[target - item] {
    			return [val, index]
    		}
    		dic[item] = index
    	}
    	return []
   }