两数之和 - 好文

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。----来源于leetcode

示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0,
1]
下面我们针对题目进行不同方式解答

第一种方式:

暴力法很简单,遍历每个元素x,并查找是否存在一个值与target - x 相等的目标元素,下面是swift代码解答,可直接运行
class Solution { var nums: [Int] = [1,4,15,16,45,86,9,8,3] let target = 17 var
tempArr= [Int]() func twoSum(_ nums: [Int], _ target: Int) ->[Int]{ for i in
0..<nums.count { for j in i+1..<nums.count { if nums[j] == target - nums[i] {
tempArr.append(i) tempArr.append(j) } } }return tempArr } }

第二种方式:

通过一遍哈希表.在进行迭代并将元素插入到表中的同时,还会回头查看表中是否已经存在当前元素所对应的目标元素.如果存在,那说明找到了对应的解,并立即将其返回.
var nums = [22,44,33,66,3,8,4,99] var target = 88 func twoSum(_ nums: [Int],
_target: Int)-> [Int] { var result = [Int]() var container = Set<Int>() for
(index, value)in nums.enumerated() { let match = target - value if
container.contains(match) { let first= nums.firstIndex(of: match)!
result.append(first) result.append(index)break } container.insert(value) }
return result } let result:[Int] = twoSum(nums, _target: target) print(result)
题解说明:

1. 创建Hash Container解决时间复杂度问题

2. 在Hash Container中查找match匹配,

　　查找成功,找到value和match的索引index

3.查找失败,将value1存入Hash Container中

4.继续遍历数组.

拓展:Set<Int>() ---为讲解

Set讲解:

* Set容器是用来存储相同类型的无序集合,而且元素是不重复的;
* 存储在Set中的元素有个限制: 元素类型必须是Hashable可哈希化
* 可快速查找
Set与数组不同的是,Set里面的元素是无序的,并且每个元素都不能重复.

上面就是两数之和的题解以及拓展知识Set的讲解,希望对大家有所帮助.

热门工具换一换