龙熠的技术小站

Leetcode : 1 Two Sum

从一组数字中找出两数相加之和等于指定数字,返回两数的下标数组


题目

1
2
3
4
5
6
7
描述
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
The return format had been changed to zero-based indices. Please read the above updated description carefully.
1
2
3
4
5
6
例子
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解题思路

指针先指向第一个数字,然后判断后面有无符合条件的数字,如果有,则返回,如果没有则往后继续遍历

先选用一个字典,将value和index反置,即字典的key是数字的值,字典的value是数字的index。

增加判断,如果target - value即value的对应值存在于字典中,则直接返回结果

如果不存在,则继续讲反置的值存入字典

时间复杂度O(N)

解题

Language : swift

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var dict: [Int: Int] = [:]
for (index, value) in nums.enumerated() {
if let f = dict[target - value] {
return [f, index]
}
dict[value] = index
}
return [-1, -1]
}
}
分享