文章目录
一、题目描述
输入一个 递增 排序的数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。如果有多对数字的和等于 s，则输出任意一对即可。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
示例 2：
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]
限制：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
二、我的题解 – 哈希表
使用哈希表作为存储结果，然后遍历。
无论是时间复杂度还是空间复杂度都有点高。
代码：
func twoSum(nums []int, target int) []int {
type n struct{} //使用空结构体当占位符
var g n
hashtable := make(map[int]n)
for _, j := range nums {
if _, ok := hashtable[target-j]; ok {
return []int{target - j,j}
}
hashtable[j] = g
}
return []int{}
}
三、双指针解法
我们可以利用题目中的数组是 递增 的特性，利用双指针分别从头尾开始寻找。
- 指针 i，j 分别指向数组的头和尾。
- 如果 j 指针指的数大于 target ，那肯定不符合题意。所以先将 j 指针向前移到
nums[j] <= target处。 - 如果
nums[i]+nums[j] < target，那就试图增大nums[i]+nums[j]，将 i 指针 ++。 - 如果
nums[i]+nums[j] > target，那就试图减小nums[i]+nums[j]，将 j 指针 –。 - 直到
nums[i]+nums[j] = target，成功找到。或者j <= i相遇或者错过，查找失败。
代码：
func twoSum(nums []int, target int) []int {
i, j := 0, len(nums)-1
for j > i && nums[j] > target {
j--
}
if j == 0 {
return []int{}
} else {
for i < j && nums[i]+nums[j] != target {
if nums[i]+nums[j] < target {
i++
} else if nums[i]+nums[j] > target {
j--
}
}
if j <= i {
return []int{}
} else {
return []int{nums[i], nums[j]}
}
}
return []int{}
}
评判结果：
表现还是相当优秀的 ~
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/118974.html
