美团算法笔试题

在平面坐标上有n个点，求两两间的斜率最大值(假设任意两点斜率都是存在的)。

解：这题的思路是先将n个点按x坐标排序，然后计算两两间斜率，斜率的最大值肯定在其中出现过。为什么是两两之间呢。见下图，1、3两点连成的线斜率不可能是最大的。

有一个先递增后递减的数组，查找里面的最大值。如[1,2,3,4,5,4,2,1]。

解：二分变种。逻辑过程要清楚，如果找到一个点比两边都大，那说明已经找到了，结束。否则，往大的那边搜。不可能比两边都小。

求数组中绝对值最接近0的连续子数组。如[-1,0,1,2,-2]中，[-1,0,-1],[2,-2],[-1,0,1,2,-2]都是满足条件的子数组。

解：之前经常遇到的题是求 和值最大的连续子数组，被思维定式了。

这题先求出前缀和数组sum[i]表示0-i项的和。
然后附上下标信息对sum进行排序，两两计算，最接近0的子数组肯定在其中出现。(因为sum[i]-sum[j] 即是 j-i项连续子数组的和)。

包含特定的字符集的最短子串。如字符集是abc，text ="cacdbe",那么text中包含abc的最短子串是acdb。

解:这次暂时只想到一个麻烦的标记方法，时间复杂度是O(n)。
待定，看能不能找到优雅的方法。 16日补：原来这题我之前是做过的，在LeetCode上，看了源码，实在麻烦的，方法还是两个指针走。