给定一个整数数组 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