哈希表

  1. (1)两数之和。使用哈希表结构，看target - nums[i], 先看这个结果有没有在哈希表中，有就返回下标，没有就插入nums[i].

  2. (2)字母异位词分组。使用哈希表结构，先遍历每一个异位词并排序把排序后的结果作为key，原异位词作为value. 最后遍历哈希表输出结果。

  3. (128)最长连续序列。也用哈希表unordered_set,因为这里只看有没有key，不需要value。插入后开始遍历原数组。

双指针

  1. (283)移动零。使用一个slow，一个fast指针。fast不为0就和slow交换。slow++。最后将slow之后的都变为0.

  2. (11) 盛最多水的容器。使用一个left,一个right指针。条件为while(left < right), 两边逼近。高度为nums[left] 和 nums[right]的min值。宽度为 right - left。每次计算并保留maxArea.

  3. (15)三数之和。暴力解法就是3个for循环遍历，每有一个符合就push_back进行vector。第二种思路本题可以先排序。然后使用for 循环遍历i。然后再剩下的采用双指针,left = i + 1, right = nums.size()- 1. 两边逼近。while(left < right) , 需要先收集答案再去重。还要进行剪枝，优化复杂度。细节比较多。

  4. (42)接雨水。

    • 这个题有两个解题思路。第一个是额外使用两个vector，一个保存左边高度，另一个保存右边高度。然后将结果相加。

    • 第二个解法就是双指针。

滑动窗口

  1. (3)无重复字符的最长字串。本题需要扩展窗口。一个left, 一个right，right用来扩展窗口。遇到有相同的字符就移动left，同时一直保存最长字串的长度。需要用一个哈希表来记录当前窗口内字符的出现情况。如果right字符出现，就一直移动left直到right没有出现过。
  2. (438)找到字符串中的所有字母异位词。有两个字串。需要先统考第一个子串的起点为，然后开始滑动窗口，遍历统计窗口内每个子串中字符出现的频率。并进行比较后滑动窗口。相等即将窗口左边下标加入vector。

子串

  1. (560) 和为K的子数组。前缀和 + 哈希表。prefix[i] = nums[o] + nums[i] + … + nums[i]; 假设子数组nums[j+1…i] 和为 k, prefix[i] - prefix[j] = k。prefix[j] = prefix[i] - k。
  2. (239)滑动窗口最大值。deque双端队列。
  3. (76) 最小覆盖子串 ?

普通数组

  1. (53) 最大子数组和。用前缀和，每一轮遍历，都计算当前前缀和，并更新最小前缀和，并计算它们差值的最大值。先计算子数组和，并更新最小前缀和。
  2. (56) 合并区间，先对区间的数组排序，使数组的第一个值是有序的，并更新计算第二个值。
  3. (238)除了自身的乘积。分别计算left 和 right 两边的积, 再相乘。
  4. (41) 缺失的第一个正整数

矩阵

  1. (73) 矩阵置0。先统计第一行和第一列中0的位置。再将第一行和第一列作为标记数组。
  2. (48)旋转图像。先上下翻转图像，在45角翻转图像。注意取值范围，上下翻转 行只取到一半。45角翻转，列要小于行的取值。
  3. (240)搜索二维矩阵。从右上角往两边搜。while(i < m && j >= 0)。

链表

  1. (160)相交链表。
    • a + b + c == c + b + a; 用链表走过一样的路程，相等的时候就是相遇的头节点
    • 用哈希表把一个链表存入，然后去遍历另一个链表。
  2. (206)反转链表。
  3. (234)回文链表。快慢指针，将后半段链表反转。注意要处理奇数个节点的情况。
  4. (2)两数相加。构造一条新链表。while(l1 || l2 || carry)
  5. (19)删除链表的倒数第N个节点。使用dummy节点，遍历时从dummy节点开始遍历，以处理要删掉头节点的状况。
  6. (148)排序链表以及合并有序链表，合并K个有序链表。
  7. (146)LRU缓存，这题要维护一个双向链表。以及一个unordered_map<int, Node*> mp; moveTohead, removeNode, addTohead, removeTail();

二叉树

  1. (94)中序遍历,dfs
  2. (104)二叉树的最大深度。1 + max(leftDepth, rightDepth)
  3. (101)对称二叉树。compare(root->left, root->right);
  4. (543)二叉树的直径。

+++

待补充…