电话面试算法问答记录
问：一个数组，先递增后递加，要返回最大的一个数，怎么实现？
答：顺次遍历第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，二分法，双指针等办法优化工夫复杂度。然而并不是单纯的靠你会不会这些办法，而是考查你是否在这些办法的根底上依据题目要求进行稍微批改，比如说第一个算法题，他用到了二分法，然而
判断条件和放大后半局部和放大前半部分要依据题目要求本人思考。
再比方如给一个有序数组和一个目标值，返回数组中大于目标值的最小数用二分法，也是对二分法的扭转。
第二道算法题用到了双指针，然而是在一层循环里应用双指针查找。