电话面试算法问答记录
问：一个数组，先递增后递加，要返回最大的一个数，怎么实现？
答：顺次遍历第 i 个数，如果第 i 个数大于第 i + 1 个数，那么返回第 i 个数，这个数就是最大值。（这么简略，大一学生都会）
问：还能优化吗？
答：啊。。。。。。
（比 o（n）工夫复杂度还快的算法就是 o（logn），那应该就是二分法，要害是怎么判断一个数是否是最大的那个数察看数组，1 2 3 4 5 4 3，如果如果第 i 个数小于第 i + 1 个数，那么阐明第 i 个数在递增那局部，最大数在后半局部，咱们放大一半范畴再去后半局部找最大数，如果第 i 个数大于第 i + 1 个数那么他有可能就是最大数，也有可能在递加那局部，如果在递加那局部，阐明最大数在前半部分，咱们放大一半范畴再去前半部分找最大数。然而如何判断是否就是最大数呢？那就再减少一个判断条件。咱们看第 i 个数，第 i – 1 个数，第 i + 1 个数三个数的法则。如果三个数顺次递增，那么第 i 个数就在递增局部，如果三个数顺次递加，那么第 i 个数就在递加局部，如果三个数顺次先增后减，那么第 i 个数就是最大数。）
应用二分法查找，设两头数下表为 i，如果第 i 个数大于第 i – 1 个数并且第 i + 1 个数大于第 i 个数，那么第 i 个数处于递增序列局部，应用后半局部数组持续进行查找; 如果第 i 个数小于第 i – 1 个数且第 i + 1 个数大于第 i 个数，那么第 i 个数处于递加序列局部，应用前半部分数组持续进行查找; 如果第 i 个数大于第 i – 1 个数并且第 i 个数大于第 i + 1 个数，那么这个数就是最大数。
问：工夫复杂度多少？
答：logn。
问：你口试那道三数之和题（给一个无序数组和一个目标值，判断数组中是否找到三个数，使三个数之和为目标值）怎么做的，工夫复杂度多少？
答：那个用了 HashMap 将数组的数 key = 值，value = 值第下表形式全副存储进去，而后用一个二重循环，一层 i 循环一层 j 循环，判断 HashMap 中是否含有（目标值 – 第 i 个数 – 第 j 个数）。工夫复杂度是 o（n^2）。
问：还有别的办法吗？
答：啊。。。。。。
（对于一个无序数组，先快排成一个有序数组，工夫复杂度为 o（nlogn），而后定义三个指针 i，j，k 初始别为 0，如果第 i 个数 + 第 j 个数 + 第 k 个数小于指标数，那么就 k ++，如果第 i 个数 + 第 j 个数 + 第 k 个数大于指标数，那么再将 k ++ 就没有意义了，那么就去去挪动 j，不对，这么做工夫复杂度还是 n^3，无非是在做剪枝工作。再想想。
对于一个固定的 i，如果初始化 j 和 k 为一个靠近的值，那么就能够更快了。有了，固定 i 为 0，设 j 为 1，k 为最大下标值 n – 1，如果第 i 个数 + 第 j 个数 + 第 k 个数大于目标值，那么就将 j ++，如果第 i 个数 + 第 j 个数 + 第 k 个数小于目标值，那么就将 k –，当 k == j 时跳出循环
将 i ++ 再次进行判断）。
设三个指针 i = 0；j = i + 1；k = n – 1；固定 i，对于寻找第二个数和第三个数应用双指针形式，如果三个指针对应数之和小于指标数，就将 j 指针向后挪动一位，如果三个指针对应数之和大于指标数，就讲 k 指针向前挪动一位。如果 j == k。那么就跳出循环，将 i ++，接着进行判断。这样工夫复杂度为 o（n^2）。
问：还有别的办法吗？
答：（面试官你别太过分！）想不到了。
总结
算法题其实大体办法比拟固定，比如说对于数组局部，能够用 HashMap，二分法，双指针等办法优化工夫复杂度。然而并不是单纯的靠你会不会这些办法，而是考查你是否在这些办法的根底上依据题目要求进行稍微批改，比如说第一个算法题，他用到了二分法，然而
判断条件和放大后半局部和放大前半部分要依据题目要求本人思考。
再比方如给一个有序数组和一个目标值，返回数组中大于目标值的最小数用二分法，也是对二分法的扭转。
第二道算法题用到了双指针，然而是在一层循环里应用双指针查找。