本文始发于个人公众号: TechFlow
今天是周末, 和大家一起来看一道算法题. 这道题是大名鼎鼎的 LeetCode 的第一题, 也是面试当中非常常见的一道面试题. 题目不难, 但是对于初学者来说应该还是很有意思, 也是一道很适合入门的算法题.
废话不多说, 让我们一起来看看题目吧.
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.
翻译
给定一个全是 int 的数组和一个整数 target, 要求返回两个下标, 使得数组当中这两个下标对应的和等于 target.
你可以假设一定值存在一个答案, 并且一个元素不能使用两次.
解答
找两个数和等于 target, 第一反应就是暴力枚举. 假设数组长度是 n, 那么一个
n2 的循环就可以搞定. 用 Python 的话, 分分钟就可以写出代码.
这样做当然是正确的, 但显然不是最好的答案. 根据经验, 一般情况下 O(n2) 的算法都不是最优解.
引入 map
如果你熟悉 C++ STL 或者其他语言工具库的用法, 想必应该很容易想到可以使用 map.map 是一个非常常用的容器, 用来存储 key-value 格式的数据对.
在这道题当中, 我们可以将元素和它在数组当中对应的下标存储进 map 当中. 也就是说我们把所有数据对应的下标存储好了之后, 我们在遍历的时候, 就可以去掉 j 那一重循环, 而直接判断 target−a[j] 在不在 map 当中即可.
我们继续写出伪代码:
这个算法看起来没什么问题, 但是如果你这么写出代码来提交一定过不了.
因为有一种隐藏的情况没有考虑到, 一般我们会把这种隐藏的不容易想到的情况称作 "Trick", 可以看做是出题人使用的诡计.
题目当中说了, 同一个元素不能使用两次, 但是并没有说数组当中没有重复的元素. map 的使用有一个限制, 就是不能有 key 值相同的元素. 如果数组当中存在重复的元素, 那么后面读到的数据会覆盖前面的. 覆盖会产生什么问题呢? 会导致我们没有办法判断元素出现的次数.
举个例子, 比如: target=6, array=[3, 3]
由于我们使用了 map, 我们在记录下第二个 3 的时候, 就会损失第一个 3 的信息. 这样我们就会错过答案, 不过这个问题也并不是不能解决, 我们可以用一个标记记录一下, 是否有重复的数字或者是重复的数字是什么. 不过这并不是完美的解决方案, 我们没有想到完美解法, 是因为有一个潜在的条件被我们忽略了.
这个条件就是加法的交换律, 也就是说 a+b=target, 那么 b+a 也应该等于 target. 这当然是一个废话, 但如果 a 和 b 之间存在顺序的话就不一样了. 如果 a 的顺序在 b 前面, 那么我们应该通过 a 去找 b 呢, 还是应该通过 b 去找 a?
当然是通过 b 去找 a, 因为 a 在 b 之前, 我们可以利用之前已经遍历过的信息查找. 如果通过 a 去找 b, 那么我们需要再开辟一个循环遍历.
想明白了这点, 剩下的就简单了.
假设数组 array 一共有 n 个元素, 分别是 a0,a1,?,an−1. 我们用一个 map 存储之前出现过的元素的下标, 当我们遍历到 i 的时候, 我们只需要判断 target−ai 在不在 map 当中即可.
因为假设存在 ai+aj=target,i<j. 当我们指针遍历到 i 的时候找不出答案, 因为 aj 的值还没有出现在 map 中. 但是当我们遍历到 j 的时候, 一定可以找到答案, 因为 ai 已经出现过了.
通过利用加法交换律以及元素出现的先后顺序, 再结合 map, 我们只需要一次遍历就可以找到答案. 就算出现重复元素, 也没有关系, 因为我们是先判断存不存在, 再更新 map.
最后, 附上伪代码:
这题本身并不难解, 用到的知识也平淡无奇, 不过要想能琢磨出其中的 trick, 并想到解法, 并不容易, 需要基于充分的思考和理解.
简单题也能有所收获, 祝大家刷题愉快.
如果喜欢本文, 请顺手给个关注吧:
来源: http://www.bubuko.com/infodetail-3356435.html