一、有时序的数组

买卖股票的最好时机，装水最多的容器两壁位置。

  • 需要进行逻辑分析。

如买卖股票的日期，核心在于在截止目前的历史最低价买，在当天卖，一次遍历即可求出最大利润；
装水容器问题，装水量=宽*高。采用贪心算法，一开始就让宽最大，两壁位置在数组两端，然后不断移动两壁位置，移动的原则是希望能得到更大的高，而高是由两壁的最小值决定，因此移动的原则是移动两壁中较小的壁，一次循环也能得到最大装水量。

子序列问题。最大和子序列，最大乘积子序列。

一般子序列问题采用动态规划方法，核心在于找到动态传递方程，从而能利用小规模问题求解大规模问题。可用滑动窗口减小动态规划的空间复杂度。

查找最值问题。寻找旋转排序数组中的最小值。

一般用二分法解决，O(log n)。二分法要注意划分依据是否有=，边界尽量right=mid-1/left=mid+1.

二、无时序的数组

找到n个互相配合的数。如，两数和为M，三数和为0，检查是否有重复等。

暴力法x重循环，O(nx)。改进有两种思路，以两数和为例。
第一种思路，注意到第二次循环是因为寻找 M-a1 的时间复杂度为O(n)，可以在第一遍遍历时用HashMap记录有哪些数字存在，可将第二次循环的时间复杂度降至 O(1)，但需要O(n)的空间复杂度。
第二种思路，先排序后，使用二分法思想，用双指针逐步向内收缩，双指针合计移动O(n)，排序需要O(nlog n)，总的时间复杂度为O(nlog n)。