哈希表-字符串

1. 哈希表-字符串

感谢代码随想录

1.1. 快乐数

快乐数

查找数字是否重复出现，使用哈希表存储

#include <set>
set<int> s;
s.insert(a); // 插入数据
if(s.find(a)!= s.end()){
    // 查找数据是否在s中
    //如果出现 != s.end(), 没出现 == s.end()
}

1.2. 两数之和

两数之和

1. map存放在之前的数据，也是当前查询中匹配的数据
2. map中key对应数值，value对应索引
3. unordered_map中使用Hash存储， map中使用红黑树存储

1.3. 三数之和

三数之和

1. 使用三个指针，查找指针对应的数据之和是否为0

2. 指针去重，结果中不能包含统一的数据，所以在取得结果后再去重，而不是先去重再计算结果

  if(i> 0 && nums[i]== nums[i-1]){
      continue;//对已有结果去重
  }

3. vector**{1， 2，3}**，使用{}作为临时vector
4. for( ; ; ) 中第一个式子只对第一次循环有效，循环中赋初值需放在循环内

2. 字符串

2.1. 反转字符串

反转字符串2

1. 对于有规律的计数时，使用i = i+ num，
2. reverse(begin()+i， begin+k)，反转范围为[i,k）

2.2. 花式反转

先反转整体，再反转局部

1. 去除空格时，sum值代表字符串的长度
2. 当s 遍历到结尾时，也是一个反转条件

2.3. KMP算法

获得next数组

1. 初始化为0
2. 如果s[i] 与s[j] 相同，最长的 j +1；
3. 否则与next[j-1]的字串进行比较；

比较

1. 如果s[i] 与t[j] 相同， j++ ，比较下一位
2. 否则返回到最长的公共子串的下一位， 即next[j-1]比较

next初值赋值为1 时，相当于next 向右移动了一位，此时不相同时，取next[j]即可

2.4. 重复子串

重复子串

结论： 如果s是由重复序列组成，那么s+s中一定具有s