1.两数之和
思路：
都会想到的肯定是两重循环，但这会导致一个n平方的时间复杂度。有一个问题是，我在看浙大数据结构课中，其中提到如果见到n平方，要想办法做成nlogn，所以思路往那边想去了。所以，什么情况下能尝试吧n平方优化成nlogn呢？
没想到的是，LeetCode给的官方解法是hashmap的方式，一次遍历，判断是否有target-nums[i]交给哈希表做就好。这样的空间复杂度是On，时间复杂度是On。还有就是，可能在map里通过value找key麻烦一些，所以key设置成了nums[i]，value设置成了i。
java中的hashmap还不太熟，需要进一步熟悉
class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } }
11. 盛最多水的容器
思路：最容易想到的思路仍然是两次遍历（事实上如果不动动脑筋，每一个数组题都是两次遍历哈哈）。但是我们直觉肯定能感觉到，在两次遍历中出现了大量无效的遍历，就是那些明明相比前一种情况面积缩水了的反而被遍历到了。
问题是，在改变高度的同时宽度也在变化。能否构造出一种情况，能让我们发现明显的面积缩水从而排除一些选择呢？关键要保证宽度不能增加，只能不变或缩小。
想到这里，就不难想到，把初始情况设置成在两侧。现在的遍历变成了两侧向中间挪，我们发现，每次移动都不能动两侧中较大的那一侧，因为会导致宽度缩减的同时，高度不变或者缩减（短端只可能更短）。想象一个分叉的选择树，我们每次选择都砍掉了一个分支。
即无论我们怎么移动右指针，得到的容器的容量都小于移动前容器的容量。也就是说，这个左指针对应的数不会作为容器的边界了，那么我们就可以丢弃这个位置，将左指针向右移动一个位置，此时新的左指针于原先的右指针之间的左右位置，才可能会作为容器的边界。
但是这样解释感觉还是有疑惑的，从两边向中间移感觉非常不直观，老是感觉不能覆盖所有的选择。这时候看到了一个非常优秀的解释：
不得不说这样看相当直观，每次移动边界就能消掉一行或者一列的可能，原本明显是n平方的遍历变为了n复杂度的。
所以本题的思想在于缩减搜索空间
public int maxArea(int[] height) { int res = 0; int i = 0; int j = height.length - 1; while (i < j) { int area = (j - i) * Math.min(height[i], height[j]); res = Math.max(res, area); if (height[i] < height[j]) { i++; } else { j--; } } return res; }