面试遇到的两个算法题

[lalala121]

1.一个整数数组，求这个整数数组中哪两个数相加等于 100，写出算法（假设数组中没有重复值，无序）。

我首先想到的是穷举，但是时间复杂度太高，pass，然后能想到的就是用 100 依次减去数组中的整数，然后再判断一下差值是否在数组中，但是面试官说还是没达到他的要求，我暂时没想出来

2.求 100 的阶乘

我能想到的就是迭代和递归两种方式，递归我知道肯定是跑不了的，跑完估计几百年以后了。迭代的话结果数字又太大，没有类型能存下，面试官问有没有更好的办法，我暂时没想出来

平时算法接触的不多，没想过这些问题，求各位提供一下思路，好让我开悟

-----------------一个正在找工作的苦逼 PHP 程序员

[stevenbipt]

第一个用哈希表就很快了，如果没记错就是 leetcode 的第一个题，第二题不太清楚

[enenaaa]

第一题， 楼主的解法， 后面检查那步如果是遍历的话， 复杂度是 O(n^2)。先排序再对向搜索， 复杂度是 O(nlogn + n)。记得 leetcode 上有这题。

第二题， 用动态规划。

[iugo]

我覺得大家想的應該都差不多.

https://gist.github.com/iugo/4e1cd5f316316f16510d3dbf0e124bd6

[stevenbipt]

第二题想了一下可能用分治法把 4 个数分为一组先进行相乘转化成科学记数法的形式，然后对每一组的数字进行乘法，10 的次方数进行相加，不过需要处理的是小数乘的时候的精度，如果能保持精度说不定能行

[enenaaa]

sorry, 第二题没仔细看题目。阶乘无法直接用动态规划解决。

[nl101531]

第一题不是 leetcode 的第一题吗？

[Daath]

第一道我能想到就是，遍历一次整数数组，把值都当做另外个字典的 key，其然后 value 加 1，初始值为 0，然后判断 100-值的差值作为字典 key 来查 value 大于 0，如果有就凑一对 print 出来。

[Daath]

当年毕业面试的时候也遇到跟这个很类似的，就只是单单问时间复杂度最小是多少

[heiybb]

记得以前在 EXCEL 里碰到过 多个值求与目标值最相近的子集和

[melissa104]

感觉用 js 好容易弄哦。。。

[larendorrx]

@stevenbipt 是的，就是 leetcode 上的，用 hash 缓存 100-x

[cgsv]

额，这些算是最基本的算法题了吧。另外求 100 的阶乘迭代和递归时间复杂度是一样的，这个不是 fibonacci 数列，递归过程没有重复的计算

[lalala121]

@cgsv 但是实际情况是，递归根本跑不完 100 的阶乘，写成递归完全没法用，空间复杂度太高了

[stevenbipt]

如果不考虑了具体精度只需要知道大概的数量级可以直接转化成 log 以 10 为底数的的和，最后出来的结果就是 10 的指数

[earendil1412]

第一题能快过 O(n)?
第二题楼主怕不是对递归和空间复杂度有什么误解

[lalala121]

@earendil1412 不知道啊，我回家用递归和迭代试了，迭代的结果转成科学计数法输出了，递归直接报错了，php 实现的

[lalala121]

@earendil1412 额，不好意思，可能是我搞错了，又试了一下，递归是可以运行的，抱歉

[hackpro]

第一题可以用桶 一个数一个坑 给定一个数 i 检查 100-i 在不在坑里就知道了
缺点是如果这题把 100 改成 100W 这方法就挂了

[LenonZeng]

100 以内不重复两个整数相加，只有 50 对 （ 0，100 ）（ 1, 99 ）（ 2，98 ）...（ 49，51 ）；将数组的值映射到位图，位图大小为最大整数值；然后，检查这 50 个对应的位的值都为 1，结果就是存在。理论只有检查 50 次，其他都是数据输入的时间。当然前提是都是正整数。