leetcode explore 初级算法第九题。原题链接:
https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/29/
原题内容如下:
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, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
题意拆解:
1、输入为一个列表,这个列表只包含数字,同时接受一个数字,这个数据为目标和。 2、找到列表中两个数相加等于目标和,并返回这两个数的下标。 3、题目前提:假设每组输入只会有一组结果输出,即只会找到唯一的一组数相加等于目标和。
注意事项: 1、同一个位置的数不能使用两次。注意是同一个位置,而不是相同的数。
其实这个问题最终可以转换为查找,我们遍历这个列表,每取一个数,如Ni,然后要通过比较高效的查找算法,去查询 (target - Ni) 在列表中是否存在,如果存在则返回这两个数的下标。
而对于高效的查找方法,我们肯定会想到用二分,而二分必须先排序,如果先排序,我们按顺序去遍历数组,可以通过二分法去查询目标和与当前数的差值在列表中是否存在,这样做时间复杂度为 O(nlogn),看上去还不错,但返回结果里需要输出的是数字在原列表中的下标,而排序后我们会改变数组的下标,好像就会有点麻烦了。
有没有另外比较高效的查找方法呢?或者说数据结构呢?显然在 Python 中 dict 是可以很高效地根据 key 去查找 value 的,但是 dict 的 key 是不能重复的,但是我们可以将 dict value 设置为 list,这样可以保留重复元素的下标值,就可以实现我们想要的效果了。参考代码如下:
from collections import defaultdict
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if not nums:
return
# 转换成 dict,这里不考虑排序再用二分,是因为最后要返回原来的下标(当然也可以实现,只是会麻烦一点)
d = defaultdict(list)
for i in range(len(nums)):
# 需要考虑有负数的情况
# if nums[i] > target:
# continue
d[nums[i]].append(i)
for num, pos in d.items():
target_pos = d.get(target - num)
if not target_pos:
continue
if target - num == num:
if len(target_pos) <= 1:
continue
return [target_pos[0], target_pos[1]]
return [pos[0], d[target - num][0]]
if __name__ == "__main__":
s = Solution()
print(s.twoSum([2, 7, 11, 15], 9))
print(s.twoSum([3, 3], 6))
print(s.twoSum([-3, 4, 3, 90], 0))
其实通过排序和二分也是可以做到的,只需要记录下原始数据的位置即可。当然这里需要注意下相同元素的情况。这里就不给出参考代码了。