所有代码详见：https://github.com/jingminglake/Leetcode
总体思路
- 技巧
（1）使用数组替换hashmap，前提是key范围有限制，很容易和数组下标对应。 key范围限制举例：（a）字母 （b）字符串长度（c）数组元素数量 （d）整数数组里的值介于最大值和最小值之间。
（2）要注意hash的key已经默认有序的这种隐藏条件，这种情况下数据结构使用vector，例如很多的bucket题目。 这种题目的特点就是key有边界。
具体题目
1. Two Sum
题意：给出整数数组和目标值target，返回数组里面两个加起来等于target的下标。 假设这种下标只有一对，且不能是同一个下标。
解：第一题。思路，如果是暴力求解，那就是对每个元素，看其余元素，如果加起来等于target就是答案， 这是个双重循环，时间复杂度O（N^2）。
优化：可以使用hash表，扫描数组，将数组的值作为key放入；然后再扫描一遍数组，对每个元素值nums[i]，尝试在哈希表里面找到target - nums[i] ，如果存在且这个值的下标不等于自己，那就是答案。 时间复杂度O（N）。空间复杂度O（N）。
进一步优化：一遍扫描。在这里为什么可以做一遍扫描。因为这个题目的本质就是从N个下标里面选出两个来； 可以这么理解，对于每个下标，它要么和它之前的一个下标组成答案，要么和之后的一个下标组成答案。那其实只要考虑正在扫描下标（记作X）之前的下标就行，因为对于后面下标， X就是它的之前下标。 如果这样还是不好理解，那么就这么理解：我们只考虑每个坐标作为pair里面的下标较大的下标的情况，那么答案一定在于其中一个下标作为pair的情况里面，只要考虑扫描元素之前的下标存不 存在互补的元素就行了，这样一遍扫描，边扫描边存入哈希表可以解决问题。 时间复杂度O（N）。空间复杂度O（N）。
438. Find All Anagrams in a String
题意： 找出s串中的p串所有Anagram（变位字，也就是同字母但顺序不同）的起始下标。
解：对于变位词，可以使用字母的种类和数量表示。
使用hash表，这里有个技巧是，如果map的类型是<char, int>，那么可以用数组来代替。
可以使用int hash[128]或者vector
还有技巧是使用两个hash表，直接使用vector的等于号就能判断是否相等。然后每次比较的时候，可以使用窗口，也就是s中的滑动子数组，每次更新s的hash表之后，立即去和p的hash表比较，即可。
645. Set Mismatch
题意：1到n里面，有一个元素重复了，同时也缺失了一个元素。
解：使用hash可以两遍循环解决。此题可以使用数组替换hashmap，hash表使用数组的前提就是key的范围有限制。此题key的限制就是1到n。
204. Count Primes
题意：此题要求出比n小的素数个数。
解：首先的思路是，一个数，如果他不可以被比自己小的数的所有素数整除，那么就是素数。如果使用暴力求解，那么当数很大的时候，会进行很多次的循环。
优化方法是使用hash表，hash表标记一个数n是否为素数。然后在知道一个数为素数后，立即从此数向后推演出不是素数的数，在hash表中提前将那些不是素数的数置为false，然后遇到false，就不必计算。
451. Sort Characters By Frequency
题意：是把string中出现最多的字符提到前面，构建新串。
解：首先把字符和其对应的次数求出来。
方法一：二分搜索树。建立一个treemap，记录字符出现次数和对应的string串。利用map的自然排序，就可以将频率自然排序。最后，组建新串，并翻转该串作为结果。 该方法缺点是map的排序花费了nlogn的时间，使整体时间复杂度上升。
方法二：先使用hash知道字符数量，然后对hashmap进行遍历，对bucket数组（string数组，字母数量映射到字母种类）进行设值。最后，组建新串的时候，可以从bucket频率从低到高，取出各种类型字母，组建相应次数。因为每个元素只处理常数次，因此时间复杂度是O（n）。
bucket数组的长度是初始化为string长度限制设置，也就是说，字符出现最多次数也不可能超过string的长度，bucket是字母数量映射到字母种类。
方法二的优化之处在于使用了字符的长度限制规律。因此字符串的mapping操作，可以使用长度为key。
508. Most Frequent Subtree Sum
题意：求子树和频率最多的那个。
解：以和作为key，以和的数量作为val。然后扫描两遍，第一遍找出val最大的那个，第二遍把key输出。
663. Equal Tree Partition
题意：求能不能只去一条边，把树分为两棵树，且两棵树和相等。
解：此题看似比较难，实际上，可以将此题转成求所有子树的和的问题。用hash表记录所有子树的和，然后看以总和的一半是否等于任意一个子结点为根的和。
注意边界条件：如果树的总和是奇数，那么此时找和除2没意义，根本就找不到分割的边。
49. Group Anagrams
题意：同构词分为一组，返回。
解：注意此题数组中的string有可能是重复的。
此题方法是：建立hash表，然后将每个单词进行排序，排序后的值作为key存到对应key的hash表中，hash表的value是未排序之前的值。
如果使用bucketsort，那么每个单词处理时间是O（w），然后每个单词处理一次，所以时间复杂度是O（n），此题时间复杂度最多为O（nlogn），否则通不过。
244. Shortest Word Distance II
题意：计算单词间最近的下标，要多次计算。
解：多次计算，所以使用hash表记录单词到所有下标的映射。所以问题转化为计算两个int数组之间最小的距离。简单思路就是两个for循环。优化的思路就是：双指针，两个数组一起遍历，每次增大其中最小的那个，只要两个数组有一个走到头就算计算结束。
560. Subarray Sum Equals K
题意：找出连续子数组和等于k的连续子数组个数。
解：暴力求解显然O（n^2）。优化的解法使用hash。
关键是理解此题其实是two sum的变种。可以先算出前缀数组和，那么接下来，我们发现，找两个下标，就能O（1）的计算substring的总和。知道两个下标就能求总和，和twoSum解法对应上了。因此把访问过的前缀数组下标存到hashmap里，每次寻找target - 当前下标对应的值，是否之前已经找过了。这样扫描一遍就可以得出结果，时间复杂度降为O（n）。
PS.注意的点是：
(1) 不止一个的组合数，例如hash表只有一个0，但是0不仅出现在一个位置。可以使用两种方法解决：一个是使用multiset来记录重复的preSum，另一个是使用hashmap，hashmap的第二个元素记录该preSum出现的次数。
(2) 使用哨兵值，保证当前preSum等于target情况下，也可以正常计算。也就是事先插入preSum为0的情况。
(3) Follow up: 求二叉树的连续路径(不经过兄弟节点的那种路径)等于k。也就是Leetcode 437。
325. Maximum Size Subarray Sum Equals k
题意：560基础上，找出最长的符合条件的subarray。
解：解法与560相似，不过hash表将记录preSum为key对应的最左边的下标，然后维持全局变量记录下当前得出的最大跨度，最终得出的就是答案。
注意：map中preSum对应的index保留是最左侧的下标，也就是说，如果map中存在preSum，那么不在加入（更新）preSum的index了。
PS. Follow up: 求二叉树的最长连续路径(不经过兄弟节点的那种路径)等于k。
523. Continuous Subarray Sum
题意：560题的基础上，区别在于，这次求k的整数倍，且区间跨度至少是2个元素。
解：看起来只变化了一小部分，但是使用起原来的方法，又要动脑筋了。一个要改的是，现在preSum之间的差可以是k的整数倍，那么我们在两边对k求余，发现preSum与之前preSum对k同余的时候相减就是k的倍数，所以，现在hash表里面只需要存储preSum对k的余数就行了。hash表的映射可以取preSum对k的余数的对应的数组中最靠近左边的下标（找不到时候就插入，找到时候并不插入）。不过一切还没结束，因为如果k为0，那么该方法失效。所以对于k为0的情况，将preSum本身存入hash表。 仍然需要哨兵值。
554. Brick Wall
题意：如图所示，给出二维数组表示墙，坐标表示砖块的位置，元素大小代表砖块的宽度。每个一维数组中砖头数量不定，但是总长度是和其他的一维数组的总长度是相等的。现在求穿过墙最少需要穿过多少砖块。
解：首先明白，沿着某个砖块边缘切才可能是最优解，但是直接暴力求解显然不好，时间复杂度高达O(N^4)。
优化方法是发现，穿过砖块最少的切割部分有一个特点，那就是砖块的边缘是对齐的，也就是说，宽度的总和相等。
实际上，这种宽度本质上是前缀和问题，每个元素右边缘都可以作为切割点，这种切割点可以作为候选者进行考虑。
所以解法是前缀数组和+hash。也就是说，首先扫描二维数组，构建每个一维数组的前缀数组和，并将和的数量存入hashmap。
结果就是从前缀和数量最多的地方。结果就是，一维数组的个数减去前缀数组和出现的最多那个的次数。
PS.不能从开头或者结束开始切，所以计算preSum时不能计算每一行最后一个元素。
525. Contiguous Array
题意：求连续子数组中包含相等的数字0和1的中最长的一个。
解：此题其实仍然是560、325的变形题，只需要把0当作-1，那么问题变为子数组和为0的问题，那么使用325题的方法就可以求解。
670. Maximum Swap
题意：求交换正整数中的两个数字，得出的最大数。
解：显然，直接解法就是暴力法，两两交换，看谁大，耗时O(N^2)。
优化方法是，每个元素只和自己最右侧的最大元素进行交换，首先从右向左扫描一遍得出每个元素最右侧的最大元素，然后在扫描一遍，每次交换得出一个最终结果的候选值。 花费时间O(N)，花费空间O(N)。
另外，（1）需要先将int转string。
（2）右侧最大元素相等的时候，选择最靠右的。
可以进一步将空间复杂度减为O(1)。技巧就是由于此题元素只是1到9的，因此使用一个大小为10的hashmap，就可以解决问题。
技巧就是先扫描一遍数组，并使用hash表记录1到9数字的所在的最靠数组右侧的下标。此题的关键是从左到右扫描，如果数组中存在比当前数字大的数字中最大数字，那么交换，返回结果即可。使用hash之后，扫描一个元素的时候，每次都从9开始比较，然后比较8，…直到不比该数字小的数，如果他们中有一个数是比当前数字靠右侧，那么交换返回结果。
274. H-Index
题意：数组里面放的是某位作者的所有论文，数组中的值表示引用次数。现在要求出数组的hIndex，hIndex是最少h篇论文引用次数大于h，剩余N-h篇论文引用次数均小于h次，h尽量要大。
解：记住hIndex的经典计算过程：先将论文引用数量从高到低进行排序，我们知道hIndex的大小必然是1到N，在排序数组中我们将其映射到数组下标，
然后我们看下标位置和所在值（引用数量的关系）：例如看第一个位置的论文引用数是否大于等于1，如果是，那么hIndex至少为1。为什么？因为至少有一篇论文引用数大于等于1，满足定义。
在看第二个位置，如果所在值大于等于2，那么至少有两篇引用数大于等于2，为什么？因为是降序排序的，第一篇论文引用数量只会大于等于第二个位置，从而大于等于2。依次类推。。。
如果i位置存在 citations[i] >= i + 1，那么hIndex >= i + 1。
再来看如果 citations[j] < j + 1 说明什么：说明最多有j篇文章（j之前所有文章）大于等于j + 1，也就是hIndex < j + 1。
所以，如果是已经降序排序好的情况下，此题的本质是搜索到最后一个citations[i] >= i + 1的点，也可以转化为搜索第一个citations[j] < j + 1的前一个点。
方法一：排序，从大到小排序，从头开始扫描，只要当前下标i所在元素的值比i大，那么hIndex++。扫描直到小于i，hIndex就是答案。时间复杂度是排序的时间复杂度。因此在此不赘用二分了。
方法二：使用hash，使用bucket的槽（0到论文种类总数）表示有key个引用的论文数。 首先扫描引用数组，如果论文引用数大于论文总数（理解：bucket上限就是论文总数，比论文总数多的引用数当作论文总数情况处理），那么论文总数个的引用数所在槽加1，否则，引用数对应的引用key下标所在槽加1。然后从尾到头扫描bucket，进行累加（累加值的意思是当前论文总数），如果发现累加值大于key，那么就立即返回作为hIndex。
方法二的本质还是先排序，只不过使用了桶排序，从而降低了时间复杂度为O(N)，但是也消耗了额外的空间O(N)。在未排序的此题中，使用方法二较好，但要本质都是需要清晰记住hIndex的经典计算过程。
PS. 理解hIndex的概念。hIndex可以代表一个人论文的影响程度，首先，一个人发表的论文越多，那么说明影响越大，hIndex也越大；
其次，也要看论文的引用数量，引用越多说明越厉害，如果发了一堆论文，但是引用数少，那么hIndex也要小。
最后，hIndex还考虑到了一个人发表论文数量少，但引用多的情况，hIndex也会适当的大。
总之，hIndex考虑了一个人发表的论文总数，以及使用论文数作引用数进行考量。
266. Palindrome Permutation
题意：判断string的排列能不能回文。
解：此题是hash题。在string长度为偶数的时候，每个元素都得是偶数的，如果string长度为奇数，那么只允许一个元素是奇数，但是其他每个元素都为偶数。
其实还有更加巧妙的方法：设置set，遇到没加入过set的，就加入，遇到加过的，就从set删除，最后看set大小，如果小于等于1，那么就返回true，否则返回false。
76. Minimum Window Substring
题意：给出串S和T，求出S中最小窗口，包含所有T中的字符：类型和数量都要包含，不要求字符顺序一致。例如:BANC可以包含BAC。
解：首先，扫描T串，存入hash表，映射关系为值到出现次数。还要保持一个count数，来记录T串的长度。
然后，双指针扫描S串，right指针如果遇到T串的一个相同字母，而且该字母出现次数仍然大于0，那么count–，hash表中相应字母次数减1。这样，我们知道，当count为0的时候，我们其实已经发现了包含T串的窗口。 count为0的时候，要做就是缩减窗口，把left指针加1，且把遇到的字母出现次数加1，同时看能不能更新窗口大小，如果遇到T串的一个相同字母，那么将其出现次数加1，并同时将count加1，退出count为0的循环。
此方法巧妙之处在于，遇到非T串的字符时候，无论加减，出现次数都不可能大于0。
容易理解的另一种方法就是：如果当前扫描字符不存在，那么直接不变，只有map存在的字符，才进行加减计算,值得注意的是左指针恢复hash字母次数的时候，如果次数是负的，那么count不加。
792. Number of Matching Subsequences
题意：给出串s和单词数组，求出满足是串s子序列的单词个数。
解：此题如果使用暴力求解，也就是对每个单词都和串s进行子序列比较，那么时间复杂度是每个单词的长度乘以s的长度，是不能通过的。
改进的方法是：
1.使用hash。扫描s，将字母映射到s对应的下标，也就是char -> vector
然后对每个单词，扫描，只需要O(1)的时间就知道当前扫描的字符合不合理，合理是指存在，而且比上一次的下标要大的前提下在vector
此方法时间复杂度是s的长度加上 （单词长度乘以s长度的log再乘以单词数），因为查找消耗log单词数时间，单词长度很小，所以基本接近线性时间。
2.使用hash结合并行指针。扫描s，找到当前扫描的字符开头的所有正在处理单词的子串部分（使用hash记录每个单词当前处理的index和单词本身所在字典的下标），那么相应单词指针往后移动一个。这样扫描完s之后，如果哪个单词的指针还没到结尾，那么就说明不是。理论上时间复杂度就是s的长度加上所有单词的长度。空间上使用一个waitinglist，长度是单词数。
676. Implement Magic Dictionary
题意：构建神奇字典，对于字典有两种操作，一个是加入新单词到字典，另一个是搜索与单词差异为1（只能修改1个字符，也就是说与单词长度一致）的串，看存不存在。
解：此题使用Trie反而比较难想。此题由于单词长度一致，那么使用hash来解决也许也可以。
hash的做法就是将单词存入的时候，依次将单词每个字符变成’#’，然后将变化的串作为key，然后原来的字符作为value。使用unordered_map<string, unordered_set
另一种解法是：将单词存入set，然后对于要查找的串，每个字母进行25种变化，然后去set中查看是否存在。
288. Unique Word Abbreviation
题意：先给出一个字典，然后要把字典按压缩的存起来，压缩规则是
解：题目比较难理解，例如字典中有deer和door的时候，如果此时查deer，应该给出的结果是false，因为字典本身的deer和door已经重复。
所以此题关键是如何知道字典中本来单词就重复了，方法就是使用map，key是压缩单词，value是原来单词。但是发现两个单词对应一个压缩形式的时候，要把value置为空。因为每次判断是不是独特的方法就是，一旦压缩形式存在，那么单词一定要等于map的value值。
249. Group Shifted Strings
题意：给出字符串数组，现在要把其中可以shift成一种的字符串放在一组，例如”abc” -> “bcd” -> … -> “xyz”都是属于可以shift成一种的串。
解：此题有个比较好的解法，就是对于每个串，构建他首位字母的距离a字母偏差的串，例如bd，由于b距离a为1，那么我们将整个串都偏移一位，变为ac。如果越界了，就加上26补回来，例如ba，那么就变为az。 这样，只需要把偏差串作为key就可以，只要是可以shift的串，最终key都是一样的。
164. Maximum Gap
题意：给出一个无序的整数数组，求该数组排好序之后，相邻元素之差最大的那个，要求时间空间复杂度都是O(n)。
解：此题如果已经排好序，那么好做，但是现在要求时间复杂度是O(n)，所以无法使用基于比较的排序。而此题是用到了桶排序，桶排序还有一个问题就是空间复杂度不为O(n)，而是O(max - min)。但是可以优化空间，使用标准化，将max - min 切分为n个区间，如果某个桶区间内有多个元素的话，那么我们只保留最大的和最小的元素(使用两个vector存储！)，最后扫描所有的桶，差的最大值是当前桶的最小值减去之前桶的最大值，为什么不用考虑桶内的大小？原因是桶的数量是元素数量个，也就是说，如果一个桶内出现有两个元素，那么必然会出现空桶的情况，那么一定存在大于桶大小的差值（桶内的差值不可能大于桶大小）。
举个例子，{0, 100}可以分为两个区间(0, 50)和(50, 100),显然100-0远远超过50。再举一个例子：{0, x, 100}，那么分为三个区间(0, 33)，(33, 66)和(66, 100)，如果x是在第一个或第三个区间里面，那么x显然不能与自己区间内的值组成最大差，如果x在第二个区间，那么每个区间只有一个元素。同理可以考虑{0, x, y, 100}。
所以，求解时候，只需要关注当前桶的最小值减去之前桶的最大值就可以了，注意的是之前的桶并不是邻居桶，因为邻居可能是空桶，
之前的桶是之前最近的有值的桶。
进行两遍扫描，第一遍要把所有的元素放到桶里面，第二遍扫描时候，只看当前结点和之前桶的差值。
不能使用边放边扫的一遍循环，因为扫描时候没办法知道右边最近的有最大值的桶是什么。
683. K Empty Slots
题意：给出n个槽，又给出大小为n的数组，数组里面装的是1到n的下标，表示第n个槽里面的花盛开。现在已知花是按照n数组的元素顺序一朵朵盛开的。求的是在哪一天花盛开的时候，距离这朵花最近的盛开的花与它的距离恰好是k，如果不存在这样的一天，那么返回-1。
解：如果使用暴力解，那么每插入一朵花，那么往左右两边看k + 1步就可以知道这一天是不是满足条件了，时间复杂度是O(n2k)， 空间复杂度O(n)。
可以进一步优化，使用平衡BST，BST里面放入盛开花的下标，那么在对当前开花的处理就是把他插入BST，然后找出他之前一个元素和之后一个元素，看他们之间的差距是不是达到了k，此方法时间复杂度为O(n * logn)，空间复杂度O(n)。
在进一步优化，设置(n + k - 1) / k个桶，分别表示1到k+1，k+2到2*k+2，…。每个桶维持一个最大值和一个最小值，然后扫描的时候，只要看当前的桶和邻居的两个桶的差距有没有达到k，具体就是之后桶的最小值与当前桶的最大值的差距以及当前桶的最小值减去之前桶的最大值。
注意：（1）不考虑桶内差距，因为桶大小安排就是k，即使端点之间距离也只是k-1。同理也不考虑非邻居桶。
（2）最小值初始化为INT_MAX,最大值初始化为INT_MIN，这样来保证不满足距离k。一旦出现数值落入桶中，那么桶的最小值最大值的初始值都会发生变化。
还有一种方法，运用到了坐标变换，将问题转化为滑动窗口问题。
题目给出的是天数到位置的数组，其实可以转化为位置到天数的数组，这样其中距离k + 1的子数组的开端和结尾就是距离为k的，这样就可以作为答案的候选者了，那么候选子数组还要满足什么条件呢？子数组中除了端点外的点要比两边的端点都大，也就是说中间位置的这些花要后开才行。这样就转化为滑动窗口问题。
注意：多个答案的情况下，返回day最小的，也就是说要看全部符合条件的子数组。
follow up：求最后连续k盆开花是哪一天。解：转化为滑动窗口问题后就简单了，找到最右的连续递增或递减的大小为k+1的子数组。
290. Word Pattern
题意：此题处理的是字符串同构的情况，但是pattern = “abba”, str = “dog dog dog dog”这种情况下是要返回false的。
解：使用hash表，但是问题是值相等时候怎么办。方法就是建立a和dog都作为关键字的两张hash表，然后使用下标作为值，这样同时扫描两个串，一开始二者对应的都是空，也符合长度只有1时候为true的情况，然后看当前扫描的字符对应的下标是不是和单词对应的下标一致，不一样就说明不是同构的。
还有一种比较好理解的方法，把字符和字符串进行双向映射，扫描过程中，如果字母单词存在，却发现有任何一个不符合映射，那么就返回false。
36. Valid Sudoku
题意：验证数独游戏的棋盘是不是合法的。
解：需要三张hash表，来记录行，列和小九宫格内是否存在1到9的数字。也就是说，例如row（1， 1）= true表示第一行存在数字1；使用col (1, 2) = true表示第一列存在数字2；grid(1,3)表示第一个小九宫格存在数字3。
扫描整个数组，每次把对应的行列，小九宫格全部标记上。不过，之前要先检查相应行列、小九宫格，如果该数已经出现了，那么说明不合法。
532. K-diff Pairs in an Array
题意：给出整数数组，求其中绝对值差距为k(k >= 0)的pair的数量，但是本题的pair是按照数字独特性来算的，不是按下标独特性来算的。
解：例如{1,3,3,1}, k = 2，那么结果就是1，因为只有{1,3}符合要求。 所以此题使用hashmap，但是不能使用边处理边计算的那种模板，因为边扫描边计算的本质是注重下标，而此题下标无意义，重要的是元素大小。
解法一：首先将所有整数存入hashmap，value部分是整数的数量。在k为0的时候，那么就看有多少个元素不止一个，那么就有多少种pair。
k不为0的时候，对每个key，只要查看比它大k的数在不在map中，有的话就加1，这样就避免了计算小k的重复情况。扫描一遍hashmap就可以得出答案。 消耗时间空间都是O(N)。
解法二：先进行排序，耗时O(NlogN)，然后使用双指针，空间降为O(1)。 k为0的时候，还是数大于两个的情况，k不为0的时候，同向双指针，右指针减左指针不够的时候就移动右指针，否则移动左指针。
