代码随想录

数组

二分查找

查找有序数组的快速方法（数组中无重复元素）

双指针法

用一个循环实现两个循环嵌套才能实现的任务

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置

滑动窗口

用两个指针分别标志窗口的起始和终止位置，用一个循环控制终止位置的移动，用判别条件控制起始位置的移动

螺旋矩阵

二维矩阵的每一圈可以拆分为四条边，为了不充分考虑四个角处，每条边左闭右开

前缀和

给定任意数组，求某个区间的和，可以先求该数组的所有前缀和，即从0到每个元素的和。那么某个区间的和就等于该区间末尾元素的前缀和减去起始元素上一个元素的前缀和

哈希表

std::unordered_map

存储键值对的数据结构，查找的时间复杂度为O(1)
创建：unordered_map<datatype,..> map
访问：map[key] 如果key不存在，则会插入一个新元素
容量：map.empty() map.size()
修改器：map.insert({key,value})插入，map.erase(key)删除
查找：map.find(key)，如果不存在则返回map.end()

两数之和问题

先在hash表中find另一个匹配的数，然后将该元素加入hash表

滑动窗口

固定滑动窗口

438.每次窗口移动时，要考虑左侧出窗口的元素的影响和右侧进窗口的值的影响，初始起始索引为0的窗口单独考虑

可变滑动窗口

3.用hash表判断是否可以向右移动指针，左指针用一个for循环枚举

二叉树

单调栈

用来找数组中每个元素后面第一个比它大的元素.
用栈维护递减元素的位置，当遇到更大的元素时，小元素出栈同时更新结果，然后大的入栈