算法题:https://leetcode.cn/studyplan/top-100-liked/
- 哈希表
- 使用哈希表,增删改查的时间复杂度均为O(1)。
- 何时使用哈希表?
- 在某个区域内查找一个已知元素,可以使用哈希表作为这个区域
- 根据一个特征对元素进行分类,特征就是key,元素就是value
- 哈希表可以去重,只需要把每个元素放入哈希表就可以了
- 使用基础类型和不可变类型(string)作为哈希表的key,不要用数组和其它变量
- 时间复杂度
- 两层for循环不一定就是 O ( n 2 ) O(n^2) O(n2),要看实际执行次数
- 双指针
- 双指针可能都从头开始,也可能一头一尾
- 在一个区域内找出特定的两个元素,需要这两个元素组合操作时,例如交换元素(快排)
- 这种多指针的问题都可以使用多层for循环很轻易地解决,但时间复杂度高,多指针可以降低时间复杂度
- 什么时候需要排序?
- 需要对数据进行某些基于顺序的操作(如查找、合并、计算前缀和等)
- 排序后可以使用一些技巧(例如双指针)可以降低时间复杂度