leetcode: explore-array-29 两数之和

用户7685359

发布于 2020-08-21 19:48:29

4080

发布于 2020-08-21 19:48:29

文章被收录于专栏：FluentStudyFluentStudy

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))

其实通过排序和二分也是可以做到的，只需要记录下原始数据的位置即可。当然这里需要注意下相同元素的情况。这里就不给出参考代码了。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-11-04，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 FluentStudy 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度