給定一個整數(shù)數(shù)組 nums 和一個目標值 target，請你在該數(shù)組中找出和為目標值的那 兩個 整數(shù)，并返回他們的數(shù)組下標。

你可以假設每種輸入只會對應一個答案。但是，數(shù)組中同一個元素不能使用兩遍。

示例:

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

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/two-sum
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

算法
swift

• 暴力法
  兩層循環(huán)，所有元素兩兩相加直到等于target
  時間復雜度為O(n^2)
  空間復雜度為O(1)

代碼

class Solution {
    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 []
    }
}

• 雙指針
  對數(shù)組排序，頭尾指針向中間靠攏
  left + right == target return
  left + right < target left ++
  left + right > target right --
  根據(jù)left 和 right 的值在原數(shù)組中找到對應的索引
  時間復雜度為O(n)
  空間復雜度為O(1)

代碼

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        // 排序
        let sortNums = nums.sorted()
        var left = 0
        var right = nums.count-1
        while left < right {
            if sortNums[left] + sortNums[right] == target {
                break
            } else if sortNums[left] + sortNums[right] < target {
                left += 1
            } else {
                right -= 1
            }
        }
        // 找到left 和 right 對應未排序數(shù)組的索引
        var result = [Int](repeating: 0, count: 2)
        for i in 0..<nums.count {
            if nums[i] == sortNums[left] {
                result[0] = i
                break
            }
        }
        for i in 0..<nums.count {
            if nums[i] == sortNums[right] && i != result[0] {
                result[1] = i
                return result
            }
        }
        return []
    }
}

• 利用字典
  循環(huán)過的數(shù)據(jù)保存在字典中[nums[i]: i]
  循環(huán)過程中判斷 keys 中是否包含 target - nums[i]
  時間復雜度為O(n)
  空間復雜度為O(n)

代碼

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        guard nums.count > 1 else {
            return []
        }
        var map = [Int: Int]()
        for i in 0..<nums.count {
            let temp = target - nums[i]
            if map.keys.contains(temp) {
                return [i, map[temp]!]
            }
            map[nums[i]] = i
        }
        return []
    }
}

GitHub：https://github.com/huxq-coder/LeetCode
歡迎star