题目主要信息:  题目给出一个长度为n的数组，其中有一个数字出现次数超过了数组长度的一半，需要我们找出这个数字 输入数组非空，保证有解，这样就不用考虑特殊情况  具体思路: 首先我们分析一下，数组某个元素出现次数超过了数组长度的一半，那它肯定出现最多，而且只要超过了一半，其他数字不可能超过一半了，必定是它。 如果给定的数组是有序的，那我们在连续的相同数字中找到出现次数最多即可，但是题目没有要求有序，一种方法是对数组排序后解决，但是时间复杂度就上去了。那我们可以考虑遍历一次数组统计各个元素出现的次数，找到出现次数大于数组长度一半的那个数字。  step 1：用unordered_map构建一个哈...

题目主要信息:  在数组中，如果有位置靠前的一个数字大于位置靠后的一个数字，则这两个数字构成一个逆序对 题目输入一个无重复数字的数组，需要求这个数组中共有多少逆序对 结果需要对1000000007取模  具体思路: 遍历数组每个数字，然后去查看它后面的所有数字是不是还有比它小的，然后统计个数，这样肯定不现实，会超时。这说明逐个统计不可行，有没有一种可能让我们一次性可以统计多个？ 逆序逆序，让我们可以想到排序将逆序去掉，什么排序方法与逆序对的交换最相关呢，大概就是归并排序了。因为我们在归并排序过程中会将数组划分成最小2个元素的子数组，然后依次比较子数组的长度，这里我们也可以用相同的方法统计逆序对...

题目主要信息:  题目给定了一个二维数组，即二维矩阵，每一行元素从左到右是递增，每一列元素从上到下是递增 需要我们判断这个矩阵中是否出现了给定数字target  具体思路: 传统的思维可能就是从上到下遍历矩阵每一行，对于每一行再从左到右遍历每个元素，然后查看target是否出现在了矩阵中，这种方法可行，但是浪费了题目给的矩阵是在一定程度上是有序的这个条件。既然矩阵每一行从左到右递增，每一列从上到下递增，那么左上角的元素一定最小，右下角的元素一定最大。我们假定遇到了矩阵中某个元素，如果它比目标值target大，那么目标值应该在它的上面或者左边，如果它比目标值target小，那么目标值应该在它的下...

题目主要信息:  斐波那契数列每项的公式为:F(n)=F(n−1)+F(n−2)F(n)=F(n-1)+F(n-2)F(n)=F(n−1)+F(n−2)，从0开始，F(0)=0F(0)=0F(0)=0，F(1)=1F(1)=1F(1)=1 求出斐波那契数列的第n项  具体思路: 既然是数列，我们就把它放入数组中来解决。  step 1：创建一个长度为n+1n+1n+1的vector数组，因为只有n+1n+1n+1才能有下标第nnn项，我们用它记录前nnn项斐波那契数列。 step 2：根据公式，初始化第0项和第1项（题目中是第1项和第2项，本质上一样的）。 step 3：遍历数组，依照公式某一...

题目主要信息:  题目给出的是一个数组和一个目标值，需要我们在数组中找到两个加起来等于目标值的数组元素的下标 下标按升序排列，从1开始  具体思路: 我们能想到最直观的解法，可能就是两层遍历，将数组所有的二元组合枚举一遍，看看是否是和为目标值，但是这样超时了，时间复杂度过于高，我们可以考虑换一种思路。O(n2)O(n^2)O(n2)的算法是遍历两次数组，这样行不通。有没有可能遍历一次数组，同时记住之前遍历过的数组元素，只要之前遍历的数组元素等于目标值减去当前遍历的元素，即找到了这两个数。  step 1：使用unordered_map构建一个哈希表，其中key值为遍历数组过程中出现过的值，va...

题目主要信息:  需要从数组num找出所有加起来等于target的组合 每个组合num中每个元素只能用1次 返回的值必须是非递减次序，组合不能重复  具体思路: 对于有序的num数组中第一个元素，我们可以考虑如果它比target大，那么后续元素都会比target大，后面就不会有加起来等于target的组合，后面都可以枝剪；但是如果它比target小，我们可以选择要不要将其加入待选路径（待选组合）中，如果没有加入，考虑下一个元素，target不变，如果加入了待选路径，考虑下一个元素的时就需要target−num[0]target−num[0]target−num[0]，由此转化成了一个子问题，递...

题目主要信息:  给定一个没有重复元素的数组看成集合，需要给出该集合的所有子集 给定的集合原本是升序，子集元素须按照升序排列  具体思路: 根据数学知识，我们可以知道nnn个元素的集合加上空集和本身一共有2n2^n2n个子集，那么可以一一枚举构造，需要做个nnn到2n2^n2n的映射。  step 1：用二进制的形式刚好可以实现nnn到2n2^n2n的映射，设置一个掩码mask，从000到2n−12^n-12n−1。 step 2：对于每个mask值都遍历一次数组，每次遍历的时候将数组下标与掩码相应的位进行比较，如果掩码该位取1，则本次子集可以取这个元素，这样根据二进制数字的特点刚好可以取完2...

哈希表介绍 哈希表是根据关键码值(key & value)而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。 在C++SLT中，哈希表的容器是unordered_map，它有一个key值与一个value值，其中可以通过key值直接访问value值，而不需要借助value值的绝对地址，因此其特点之一就是直接访问，时间复杂度为O(1)O(1)O(1)。同时，key值具有唯一性，不会存在重复的key值，且是无序的。 注：C++STL中，容器map实际上是红黑树，可以看成在哈希表的基础上增加了对key值的排序，因此其每次操作的复杂度都是O(log2n)O...

题目主要信息:  题目给定一个数组，要找到其中最长的无重复的子数组的长度 子数组必须是数组中连续的一段  具体思路: 既然要找一段连续子数组的内不重复的长度，我们可以使用滑动窗口，窗口内都是不重复的，然后窗口右界不断向右滑，如果窗口内出现了重复数组，说明新加入的元素与之前的重复了，只需要窗口左界也向右收缩就可以保证窗口内都是不重复的。那快速查询是否重复的任务就可以交给我们的哈希表了。  step 1：使用unordered_map构建一个哈希表，用于统计数组元素出现的次数。 step 2：窗口左右界都从数组首部开始，每次窗口优先右移右界，并统计进入窗口的元素的出现频率。 step 3：一旦右界...

题目主要信息:  题目给定一个无序整型数组，没有重复元素，可能有负数或零，需要找出其中没有出现的最小正整数  具体思路: n个长度的数组，没有重复，则如果数组填满了1～n，那么缺失n+1，如果数组填不满1～n，那么缺失的就是1～n中的数字。对于这种快速查询某个元素是否出现过的问题，还是可以使用哈希表。  step 1：使用unordered_map构建一个哈希表，用于记录数组中出现的数字。 step 2：从1开始，遍历到n，查询哈希表中是否有这个数字，如果没有，说明它就是数组缺失的第一个正整数，即找到。 step 3：如果遍历到最后都在哈希表中出现过了，那缺失的就是n+1.  代码实现: cl...

题目主要信息:  题目给定一个整型数组，其中有两个数字只出现了1次，其余数字都出现了两次，需要找到这两个数字 输出按照非降序排列  具体思路: 既然要找出唯二出现次数为1的两个数字，那我们可以直接统计数组中各个数字出现的次数，然后找出次数为1的两个就可以了。  step 1：用unordered_map建立一个哈希表，用来统计数组每个元素出现的次数。 step 2：遍历数组，使用哈希表计数。 step 3：遍历哈希表，找到频率为1的两个数字录入输出数组。 step 4：比较输出数组两个元素大小，交换次序做到降序输出。  可以参考如下图示：  代码实现: class Solution { pub...

题目主要信息:  题目要求为找到给定字符串数组中出现次数前k的字符串，按照出现频率由高到低排序输出，相同频率按照字典序 字符串的字符仅包含数字字母  具体思路: 很明显，这道题有两个要解决的问题，一个是统计各个字符串的出现频次，一个是找到出现次数前k的字符串然后输出。 对于第一个问题，统计频次可以使用unordered_map来实现，key值记录各个不同的字符串，value值记录其出现的次数，这是哈希表的一个操作。 对于第二个问题，可以考虑对统计好的频次排序，但是这样复杂度会比较高，因此我们只需要前k个，而不需要完整的排序，因此可以使用一个大小为k的优先队列，队列中记录的就是频次为k的字符串，...

题目主要信息:  题目给出一个长度为n的数组，其中有一个数字出现次数超过了数组长度的一半，需要我们找出这个数字 输入数组非空，保证有解，这样就不用考虑特殊情况  具体思路: 首先我们分析一下，数组某个元素出现次数超过了数组长度的一半，那它肯定出现最多，而且只要超过了一半，其他数字不可能超过一半了，必定是它。 如果给定的数组是有序的，那我们在连续的相同数字中找到出现次数最多即可，但是题目没有要求有序，我们还要统计每个数字出现次数的情况，就可以考虑使用unordered_map来统计。  step 1：用unordered_map构建一个哈希表，统计数组元素各自出现了多少次，即key值为数组元素，...

题目主要信息:  题目给出的是一个数组和一个目标值，需要我们在数组中找到两个加起来等于目标值的数组元素的下标 下标按升序排列，从1开始  具体思路: 我们能想到最直观的解法，可能就是两层遍历，将数组所有的二元组合枚举一遍，看看是否是和为目标值，但是这样太费时间了，既然加法这么复杂，我们是不是可以尝试一下减法：对于数组中出现的一个数a，如果目标值减去a的值已经出现过了，那这不就是我们要找的一对元组吗？这种时候，快速找到已经出现过的某个值，可以考虑使用哈希表，即STL提供的unordered_map。  step 1：使用unordered_map构建一个哈希表，其中key值为遍历数组过程中出现过...