82. LeetCode.1. 两数之和
2019-03-05 本文已影响7人
月牙眼的楼下小黑
-
标签：
数组双指针哈希表 -
难度：
简单
- 题目描述
- 解法： 哈希表
遍历数组，每访问一个数，就在前面访问过的数中查找是否有其补数。为了提升查找效率，利用哈希表存储访问过的数。
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
search = {}
for i, n in enumerate(nums):
if target - n in search:
return [search[target-n], i]
search[n] = i
82. LeetCode. 两数之和 II - 输入有序数组
-
标签：
数组双指针哈希表 -
难度：
简单
- 题目描述
- 解法： 双指针
先排序， low 和 high 分别指向数组开头和结尾。 如果 nums[[low] + nums[high] < target, 则 low 指针前移；如果 nums[[low] + nums[high] > target, 则 high 指针后退；相等则返回.
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
low , high = 0, len(numbers) - 1
while low < high:
sum = numbers[low] + numbers[high]
if sum == target:
return [low + 1, high + 1]
elif sum < target:
low += 1
else:
high -= 1
