算法所需的性质
1.有序/无序:sort :哈希降低查找时间复杂度/双指针来二分
2.连续:起始与结束 :滑动窗口
3.重复:没有一样的值 :通过集合unordered_set来去除重复值/通过排序跳过重复
哈希表unordered_map的使用场景
1.强化数组下标与值的关系,在原先只能通过下标找值,使用哈希表能够通过值来知道对应的下标
sort
1.sort是对目标进行一个排序,可以对vector,string排序得到一个有序值
string
1.对于string进行排序,可以得到一个有序的字符串
2.异位字符串,即对两个字符串排完序后二者相同。可以通过vector来存储各自字母出现次数,然后判断两个vector是否相等
reverse
reverse是用于翻转顺序容器的,有时可以实现O(1)的空间复杂度轮转数组
vector
1.对于连续的容器的处理,可以将区间划分,其实滑动窗口也是这个思想,从大区间划分为小区间,也可以将一整段区间分为左右区间
除自身以外数组的乘积
2.对于空间复杂度有要求的,一般都是直接使用自身的空间或者假设几个变量或者固定大小的容器(26,2),否则一定会是 > O(n)
缺失的第一个正数
这一题需要发现一个关键点:答案x的区间是一定在 1 ≤ x ≤ n + 1的,并且为了使得空间复杂度为O(1),所以面临的选择只能是利用自身的空间,把自身当做一个哈希表来存储,如何将一个数组强化到哈希表,那么就需要能够直接通过下标直到该位置的值,也就是假如下标是i,那么nums[i]的值是i,i+1,i-1这种已知的公式的值