刷题并记录。
1 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。（简单）
方法一：
复杂度为o(n^2),直观反映是这么写，下面是优化的其他方法
方法二：用字典，复杂度降为O(n)
方法三：单循环
2 链表求和
解决方法
方法一：最最基础的方法，关键点是链表的操作。也就是红色框路面，
3 无重复字符最长字串长度：
方法一：暴力
方法二：滑动窗口
滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i,j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。使用 Hash表将字符存储在当前窗口 [i,j)（最初 j=i）中。 然后我们向右侧滑动索引 j，如果它不在 Hash表中，我们会继续滑动 j。直到 s[j] 已经存在于 Hash表中。此时，我们找到的没有重复字符的最长子字符串将会以索引 i开头。那么为什么叫做滑动窗口呢？大家可以看到，上面的暴力法，我们做了很多无用的计算，在区间[i,j)中，假如我们判断是存在重复字符，那么以i开头，并且结尾大于j的所有区间都是存在重复字符的。举个例子，在【0，5）这个区间是存在重复字符的，那么在【0，6），【0，7）...一直到末尾的所有区间都会是存在重复字符的。这个时候我们就没必要进行判断了，可以直接进行i+1的操作，所以大家会发现，每次操作要么j+1，要么i+1，整个区间就像是在滑动一样，所以就要滑动窗口.
网友评论