LeetCode - 1. 两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法
swift

• 暴力法
  两层循环，所有元素两两相加直到等于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 []
    }
}

• 双指针
  对数组排序，头尾指针向中间靠拢
  left + right == target return
  left + right < target left ++
  left + right > target right --
  根据left 和 right 的值在原数组中找到对应的索引
  时间复杂度为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 对应未排序数组的索引
        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 []
    }
}

• 利用字典
  循环过的数据保存在字典中[nums[i]: i]
  循环过程中判断 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