2-刷题记录

哈希表

一般哈希表是用来快速判断一个元素是否出现在集合里。数据规模是dataSize，哈希表的大小为tableSize。

• 哈希碰撞：两个东西映射到了用一个索引下。

  • 拉链法：将发生冲突的元素都被存储在链表中。关键是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。
  • 线性探测法：一定要保证tableSize > dataSize，才能依靠哈希表中的空位来解决碰撞问题。

• 底层实现（todo）

• 数组 VS set VS map （todo）、

  • 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
  • set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

1. 有效的字母异位词

   1. 初始化一个数组，用来存放可能出现在数组中的字母对应的ASCII编码-‘a’下标的次数。如果数组中每个下标对应的元素都为0，则返回true，否则为false
   2. 数组的索引必须是int，但是哈希表的键可以是任意对象；但是数组内存占用较低，更节省内存。
   3. 在本题中，相当于已知位置访问，使用数组实现。但如果是基于内容查找，使用哈希表实现。

2. 两个数组的交集

   1. 哈希表：
      1. hashset，自动去重，使用contains(element)方法
   2. 数组：如果增添了数值范围，那可以用数组来做哈希表
      1. 一个数组，一个链表：一个数组用参数中的其中一个数组元素做下标，size为1001；一个List做存放答案
      2. 遍历完参数中的其中一个数组之后，遍历另一个参数数组，看这个元素对应的数组下标下的元素是否为0
      3. 注意最后把List转换为int[]，还要注意不重复的问题（已经加入List后，将该下标对应的元素重新置0，不再符合交集条件）

3. 快乐数

   1. 从无限循环出发：即如果出现了重复的sum值，那么最后肯定会无限循环。
   2. 计算每个位置上的平方，把sum存进hashSet，while（setR.contains(sum)），最后肯定会陷入循环，退出；否则结果一定会算出为0。结合结果为1的情况。
   3. 逻辑问题：一定要等到判断结束后，再add新的sum值

4. 两数之和

   1. 思路调整：肯定不是常规思路遍历，那就是拿着target-nums[i]反向找元素，看这个元素是否是遍历过的，map中没有，新加。有，就要提出来返回答案。
   2. 注意选数组实现、map、set？

5. 四数相加II

   1. 思路调整：四数相加和为0出发，四个数组太多，分而治之，两个一组，什么情况下能够相加为0？前两个数组的和，能够在后两个数组之后中找到对应的0 -（A+B），主要还要保留次数信息，key-value的选用
   2. 错误题解：没有理解好前两个数组之和出现的次数，到底在题目中起到什么样的作用，这个次数可以匹配所有跟他能匹配的相反数。区分两个数组的交集那个题。

6. 赎金信

   1. 直接思路：一个hashMap保存杂志字符串的字符和出现次数，遍历赎金字符串，看是否存在，注意命中后，杂志map对应Key的value要-1。
   2. 因为索引是小写字母，所以也可以用哈希数组来做，空间会小一些。

7. 三数之和

   1. 使用哈希法，在哈希表中寻找 0-（a+b），但问题是后面的去重比较困难

   2. 使用双指针法，先将数组排序，有三个下标，外层for循环对应的i，双指针法对应的left和right，初始情况下，left = i+1；right= nums.length-1;

      1. 计算nums[i]+nums[left]+nums[right]，如果>0，right向左移动；如果<0，left向右移动。直到left与right相遇

      2. 去重逻辑，不要漏掉b、c的去重

8. 四数之和

   1. 与三数之和是一样的思路，均采用双指针法，只是要多套一层for循环，把nums[i]+nums[j]作为定值
      1. 剪枝操作，一定不可能存在的情况是什么，直接return。注意每一级下的剪枝逻辑，直接return可能会有漏解。
      2. 如果nums[i]+nums[j]+nums[left]+nums[right]><=target，讨论
      3. 去重逻辑

字符串

1. 反转字符串

   1. 双指针
   2. 交换

2. 反转字符串II

   1. 依旧双指针，但是此时i+=2*k
   2. 还要注意end的赋值，尤其是最后一个窗口

3. 翻转字符串里的单词

   1. 首先去除首尾空白
   2. 双指针法，倒序遍历
      1. i，j均指向最后字符，i往前走，直到遇到空格，确定首个单词，把i+1,j之间的字符+‘空格加入新的字符串
      2. i，j继续往前走，走到非空格的地方
      3. 这样，最后一个单词后面会有额外的空格，所以最后返回的时候要删除。

4. 实现strStr()

   1. KMP算法：当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。
      1. 构造next数组
   2. 关于题目：
      1. 需保存字符出现的第一个位置，到时候匹配到，可以直接减去模式串的长度
      2. 细节问题

5. 重复的子字符串

   1. 思路拓展：能否在S+S字符串中找到原字符S（不包含头尾）

      1 2 3 4 5 6

      class Solution { public boolean repeatedSubstringPattern(String s) { String str = s + s; return str.substring(1, str.length() - 1).contains(s); } }

   2. 结合KMP算法：当字符串s的长度可以被其最长相等前后缀不包含的长度整除时，不包含的子串就是s的最小重复子串。

      1. 证明：T是重复子串
      2. 证明：T是最小重复子串