Leetcode热题100 Day2

六、三数之和

这一题最关键的想法是把第二层嵌套和第三层嵌套合并为同一层嵌套，合并后即可使用两指针法。但是即使这样我在写的时候还是花了很多时间，一个是边界条件的处理（尤其是连续有相同值的处理）以及我发现了leetcode的编译器和本地的编译器不一样：本地没有进行越界检查，但是leetcode是开启了的。

七、无重复字符的最长字串

运用滑动窗口。为什么可以滑动窗口？因为字串起始位置递增时，结束位置也一定递增！边界条件比较麻烦，花了一些时间进行修改。

八、找到字符串中所有字母异位值

仍然是采用滑动窗口，窗口的大小是固定的。窗口的特性是窗口内所有字母的出现次数，因为是异位值，所以只要出现次数相同即可，并不需要考虑出现的顺序。

九、和为K的子数组

前缀和+哈希表优化。

十、最大子数组和

方法一：动态规划。以当前位置结束的最大子数组和一定是以前一个位置结束的最大子数组和+当前值或者当前值。由此可以构造出转移方程。时间复杂度为O（n）。

方法二：前缀和。子数字和等于两端前缀和之差，所以可以遍历一遍，记录当前点之前的最小前缀和。

十一、合并区间

两指针思想。首先需要对原先的区间进行排序，排序的原则是先按照左端从小到大，左端相同则看右端。这样的话，用两个指针表示当前的已合并区间的左端和右端，不断判断这个右端是否大于下一个区间的左端，如果大于，则合并。

十二、轮转数组

比较容易观察我们需要把结尾k个元素照搬到开头。朴素的想法是构造一个新数组，然后赋值。如果想要原地操作，我们可以先反转整个数组，再对开头k个反转和后面的反转。

十三、除自身以外数组的乘积

比较朴素。

十四、矩阵置零

朴素。但是可以把空间复杂度降到O（1），不过我懒得看了。

十五、螺旋矩阵

就是螺旋遍历，上下左右四个边界定义好即可。