今日任务：

1. LeetCode28 找出字符串中第一个匹配项的下标
2. LeetCode459 重复的子字符串
3. 字符串总结
4. 双指针回顾



> 今日心情：意识到了写博客的重要性，能够快速帮我回溯记忆。

资料来源：

1. [代码随想录 | 字符串：总结篇](https://programmercarl.com/%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%80%BB%E7%BB%93.html#%E4%BB%80%E4%B9%88%E6%98%AF%E5%AD%97%E7%AC%A6%E4%B8%B2)
2. [代码随想录 | 双指针总结篇](https://programmercarl.com/%E5%8F%8C%E6%8C%87%E9%92%88%E6%80%BB%E7%BB%93.html#%E6%95%B0%E7%BB%84%E7%AF%87)
3. [代码随想录 | 28. 实现 strStr()](https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
4. [代码随想录 | LeetCode459 重复的子字符串](https://programmercarl.com/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)

### 1 KMP简述

#### 1.1 KMP是什么？

KMP是一种针对字符串的算法，因为发明者为Knuth，Morris和Pratt三位学者，所以取名KMP。它的作用是**当字符串匹配失败时，在下一次的匹配中能够获取部分已经匹配的字符串，从而避免再次从头开始匹配**。如果是用暴力来在字符串中寻找匹配字符串，那么显而易见就是两轮循环，KMP可以利用最长相等前后缀来减少循环次数。

#### 1.2 最长相同前后缀

- 前缀：字符串的必须包含第一个字符，必须不包含最后一个字符的所有子串。
- 后缀：字符串的必须包含最后一个字符，必须不包含第一个字符的所有子串。

以字符串`aabcdaa`为例，它的所有前缀包括：

1. a
2. aa
3. aab
4. aabc
5. aabcd
6. aabcda

同理，所有后缀包括：

1. a
2. aa
3. daa
4. cdaa
5. bcdaa
6. abcdaa

在这些前后缀中，最长相同前后缀即为`aa`，长度为2。

#### 1.3 前缀表

前缀表，即为字符串的所有前缀的下标和最长相同前后缀的长度组成的表，还是以字符串`aabcdaa`为例，它的前缀表是这样的：


| 字符 | a | a | b | c | d | a | a |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 最长相同前后缀的长度 | 0 | 1 | 0 | 0 | 0 | 1 | 2 |


#### 1.4 KMP匹配过程

以在字符串`aabaabaafaab`（文本串，变量名一般是`haystack`）中匹配`aabaaf`（模式串，变量名一般是`needle`）为例。

1. 求模式串的前缀表
    
    | 字符 | a | a | b | a | a | f |
    | --- | --- | --- | --- | --- | --- | --- |
    | 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
    | 最长相同前后缀的长度 | 0 | 1 | 0 | 1 | 2 | 0 |
    
2. 开始循环匹配，每次匹配失败后，文本串从匹配失败后的位置开始，模式串以匹配失败的位置的前一个元素在前缀表中存储的最长相同前后缀的长度为下标开始下次匹配，直到匹配成功。

![cc8e05d80c6e07d2fc0ad7be1d07617.jpg](https://www.misaka19327.cc/static/img/8307d5963593628b4da9f771d9300736.cc8e05d80c6e07d2fc0ad7be1d07617.jpg)

#### 1.5 为什么KMP能够提升速度 && 为什么是前缀表

KMP能提升速度的原因在于，比起暴力两层循环，KMP需要的是对模式串的一次循环和实际匹配过程中的一次循环。后一次循环还能靠前缀表来减少匹配次数。KMP的时间复杂度是$O(m+n)$，这比暴力的$O(m+n)$要快多了。

前缀表的含义是每一个字串前后相同字符的长度，它代表了KMP最根本的目的：**在下一次的匹配中能够获取部分已经匹配的字符串**。前缀表所存储的最长相同前后缀就是这句话中的“部分已经匹配的字符串”。因为最长相同前后缀的含义，下一次循环开始时，在这次匹配点之前的字符都不再需要匹配，只需要从上一次循环匹配失败的点再次开始即可。

![f10c7f5ed4c118c7f527995ff869a3f.jpg](https://www.misaka19327.cc/static/img/b06bfa6c5acf38440ad65ed9b75ea274.f10c7f5ed4c118c7f527995ff869a3f.jpg)



### 3 字符串总结

字符串，在大部分的语言中的底层实现都是基于类似字符数组的形式。在用python解题时，更应该将其转换为`List[str]`，一个字符一个字符组成的列表来处理。

:::note{title="注"}
预留Java字符串的底层机制
:::

:::note{title="注"}
预留Go字符串的底层机制
:::

1. **双指针法**：典型代表就是反转字符串，两头的指针交换并且向中间移动；或者各种形式的扩充字符串，一个指针从最后往前，一个指针从实际内容往前；或者**各种形式的删除内容，两个指针一起从头往后移动，遇到要删除的元素就快指针+1慢指针不动，遇到不是要删除的元素就交换元素然后两个指针一起+1**。
2. **反转法**：一个是要注意，反转的取值范围，如何控制边界条件；一个是可以**通过先反转全部再反转部分来达到保持部分顺序不变的同时整体顺序反转，或者两次反转顺序反过来也有奇效**。
3. **KMP**：KMP的特点是当字符串匹配时，可以获取一部分上次的匹配信息，以避免这次次匹配时从头开始。它是字符串类题目的重点。

### 4 双指针回顾

双指针是个极其广泛的解法类型，它的最终目标是利用好两个指针，在一次循环内完成两次循环要做的事情。

1. **数组**：典型就是删除元素，两个指针一起从头往后移动，遇到要删除的元素就快指针+1慢指针不动，遇到不是要删除的元素就交换元素然后两个指针一起+1。如果暴力解法就是两次循环，利用双指针就是一次循环足矣。
2. **字符串**：见上。
3. **链表**：一个典型应用是反抓链表（那题我记得好像是三个指针来着？），另一个就是**利用步长不同的两个指针来探测是否存在环以及寻找环的入口**。
4. **N数之和**：

基本上粗体的就是我一开始想不到，并且预感自己绝对会忘的东西😂

代码随想录算法训练营第九天 | LeetCode28 找出字符串中第一个匹配项的下标、LeetCode459 重复的子字符串

今日任务：

1. LeetCode344 反转字符串
2. LeetCode541 反转字符串 Ⅱ
3. 卡码网54 替换数字
4. LeetCode151 反转字符串中的单词
5. 卡码网55 右旋字符串



> 今日心情：在先翻转全部，然后翻转部分这个思路上踩了两次坑，这个要记住。

资料来源：

1. [代码随想录 | LeetCode344 反转字符串](https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
2. [代码随想录 | LeetCode541 反转字符串 Ⅱ](https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
3. [代码随想录 | 卡码网54 替换数字](https://programmercarl.com/kama54.%E6%9B%BF%E6%8D%A2%E6%95%B0%E5%AD%97.html#%E6%80%9D%E8%B7%AF)
4. [代码随想录 | LeetCode151 反转字符串中的单词](https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
5. [代码随想录 | 卡码网55 右旋字符串](https://programmercarl.com/kama55.%E5%8F%B3%E6%97%8B%E5%AD%97%E7%AC%A6%E4%B8%B2.html)

### 1 LeetCode344 反转字符串

:::info{title="题目"}
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。


示例 1：
```
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
```
示例 2：
```
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
```

提示：

* 1 <= s.length <= 105
* s[i] 都是 ASCII 码表中的可打印字符
:::

大体思路就是前后两个指针，从头尾往中间去，一边走一边交换，这说是双指针我觉得也行。

另外就是文档里写到的：**如果题目的关键部分用了库函数就能解决，那么就不要用库函数；如果库函数只是这个题目考察重点的一部分，且已经了解库函数的实现原理，那么可以使用库函数。**

``` python
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        first, last, temp = 0, len(s) - 1, 0
        while first < last:
            temp = s[first]
            s[first] = s[last]
            s[last] = temp
            first += 1
            last -= 1
```          

### 2 LeetCode541 反转字符串 Ⅱ

:::info{title="题目"}
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
 

示例 1：
```
输入：s = "abcdefg", k = 2
输出："bacdfeg"
```
示例 2：
```
输入：s = "abcd", k = 2
输出："bacd"
```

提示：

* 1 <= s.length <= 104
* s 仅由小写英文组成
* 1 <= k <= 104
:::

大体思路就是先计算要翻转的次数，按照次数进行翻转。翻转完成后，如果剩下的是k到2k的部分，就不处理直接加入数组；如果是0到k的部分，就翻转。

踩坑：

![image.png](https://www.misaka19327.cc/static/img/6aa3a6708d955912f6d8bda5afb5e0c5.image.png)

另外注意代码里的列表转字符串写法：`''.join(list)`。

``` python
# 我的代码
class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        return_str = []
        reverse_count = int(len(s) / k)
        if reverse_count % 2 == 0:
            reverse_count = int(reverse_count / 2)
        else:
            reverse_count = int(reverse_count / 2) + 1
        print(reverse_count)
        pointer = -1
        for _ in range(reverse_count):
            pointer += k
            for i in range(k):
                return_str.append(s[pointer - i])
            for i in range(k):
                if pointer + i + 1 < len(s):
                    return_str.append(s[pointer + i + 1])
            pointer += k
        if pointer < len(s):
            for i in range(len(s) - pointer - 1):
                return_str.append(s[len(s) - 1 - i])
        return ''.join(return_str)
``` 

### 3 卡码网54 替换数字

:::info{title="题目"}
题目描述
> 给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。

输入描述

> 输入一个字符串 s,s 仅包含小写字母和数字字符。

输出描述

> 打印一个新的字符串，其中每个数字字符都被替换为了number

输入示例

> a1b2c3

输出示例

> anumberbnumbercnumber

提示信息

> 数据范围：
1 <= s.length < 10000。

:::

:::tip{title="提示"}
一点小技巧：大多数数组填充类的题，可以先扩充数组到目标长度，然后从最后往前开始填充试试。
:::

先遍历所有字符，找到数字，计算扩充后应有的长度，然后扩展数组，并且按从后往前的顺序开始从字符串的最后填充到数组的最后。

``` python
a = input()
first_pointer = len(a) - 1
str_list = list(a)
more_number_len = 0
for i in a:
    if 48 <= ord(i) <= 57:
        more_number_len += 5
str_list += ['0'] * more_number_len
last_pointer = len(str_list) - 1

for first_pointer in range(first_pointer, -1, -1):
    if 48 <= ord(str_list[first_pointer]) <= 57:
        str_list[last_pointer] = "r"
        last_pointer -= 1
        str_list[last_pointer] = "e"
        last_pointer -= 1
        str_list[last_pointer] = "b"
        last_pointer -= 1
        str_list[last_pointer] = "m"
        last_pointer -= 1
        str_list[last_pointer] = "u"
        last_pointer -= 1
        str_list[last_pointer] = "n"
        last_pointer -= 1
    else:
        str_list[last_pointer] = str_list[first_pointer]
        last_pointer -= 1
print("".join(str_list))
```

### 4 LeetCode151 反转字符串中的单词

:::info{title="题目"}
给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

 

示例 1：
```
输入：s = "the sky is blue"
输出："blue is sky the"
```
示例 2：
```
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
```
示例 3：
```
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
```

提示：

* 1 <= s.length <= 104
* s 包含英文大小写字母、数字和空格 ' '
* s 中 至少存在一个 单词
:::

删空格部分不提，大致的思路就是先翻转所有的字符，然后按照单词一个一个翻转，就能把单词顺序翻转的同时，不改变单词内字符的顺序。

只是，在删空格部分被爆杀。

``` python
class Solution:
    def reverseWords(self, s: str) -> str:
        str_list = list(s)
        i = 0
        while True:
            i += 1
            if i >= len(str_list): # 因为是边查边删 for容易越界
                break
            if ord(str_list[i]) == 32:
                if ord(str_list[i - 1]) != 32: # 单词之后的一个空格可以留
                    continue
                str_list.pop(i)
                i -= 1
        if ord(str_list[0]) == 32: # 检查开头
            str_list.pop(0)
        if ord(str_list[len(str_list) - 1]) == 32: # 检查结尾
            str_list.pop(len(str_list) - 1)

        first_pointer = 0
        last_pointer = len(str_list) - 1
        while first_pointer < last_pointer:
            temp = str_list[first_pointer]
            str_list[first_pointer] = str_list[last_pointer]
            str_list[last_pointer] = temp
            first_pointer += 1
            last_pointer -= 1

        first_pointer, last_pointer = 0, 0
        while first_pointer < len(str_list) - 1:
            # 先让后指针找到要翻转的词的末尾
            for last_pointer in range(last_pointer, len(str_list)):
                if last_pointer == len(str_list) - 1:
                    break
                if ord(str_list[last_pointer]) == 32:
                    last_pointer -= 1
                    break
            temp2 = last_pointer

            # 翻转词
            while first_pointer < last_pointer:
                temp = str_list[first_pointer]
                str_list[first_pointer] = str_list[last_pointer]
                str_list[last_pointer] = temp
                first_pointer += 1
                last_pointer -= 1

            # 再找到下一个词
            if temp2 == len(str_list) - 1:
                first_pointer = temp2
            else:
                first_pointer = temp2 + 2
                last_pointer = temp2 + 2

        return "".join(str_list)
```

### 5 卡码网55 右旋字符串

:::info{title="题目"}
题目描述
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。 

例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。

输入描述
> 输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。

输出描述
> 输出共一行，为进行了右旋转操作后的字符串。

输入示例
> 2
> 
> abcdefg

输出示例
> fgabcde

提示信息
数据范围：
* 1 <= k < 10000,
* 1 <= s.length < 10000;
:::

属于是刷过前几题之后应该想到的，失算了，然后在错误的思路上狂奔。我的思路还是太过欠考虑，最后还是没做出来。实际上正确的解法和LeetCode151是一致的，先翻转所有，再按段翻转。

另，该思路也可活用于左旋，道理是差不多的。

``` python
# 我的代码
num = int(input())
str_list = list(input())

sub_num = len(str_list) - num
first_pointer, last_pointer = 0, 0 

if sub_num >= num:
    first_pointer = len(str_list) - 1
    last_pointer = sub_num - 1
    while first_pointer > 0:
        temp = str_list[first_pointer]
        str_list[first_pointer] = str_list[last_pointer]
        str_list[last_pointer] = temp
        print(str_list)
        if last_pointer > 0:
            last_pointer -= 1
        elif last_pointer == 0 and sub_num == num:
            break
        first_pointer -= 1
elif sub_num < num:
    first_pointer = sub_num
    last_pointer = 0
    while last_pointer != len(str_list) - 1:
        temp = str_list[first_pointer]
        str_list[first_pointer] = str_list[last_pointer]
        str_list[last_pointer] = temp
        if first_pointer < len(str_list) - 1:
            first_pointer += 1
        last_pointer += 1

print("".join(str_list))
```

``` python
num = int(input())
str_list = list(input())

first_pointer = 0
last_pointer = len(str_list) - 1
while first_pointer < last_pointer:
    temp = str_list[first_pointer]
    str_list[first_pointer] = str_list[last_pointer]
    str_list[last_pointer] = temp
    first_pointer += 1
    last_pointer -= 1
    
first_pointer = 0
last_pointer = num - 1
while first_pointer < last_pointer:
    temp = str_list[first_pointer]
    str_list[first_pointer] = str_list[last_pointer]
    str_list[last_pointer] = temp
    first_pointer += 1
    last_pointer -= 1
    
first_pointer = num
last_pointer = len(str_list) - 1
while first_pointer < last_pointer:
    temp = str_list[first_pointer]
    str_list[first_pointer] = str_list[last_pointer]
    str_list[last_pointer] = temp
    first_pointer += 1
    last_pointer -= 1

print("".join(str_list))
```

代码随想录算法训练营第八天 | LeetCode344 反转字符串、LeetCode541 反转字符串 Ⅱ、卡码网54 替换数字、LeetCode151 反转字符串中的单词、卡码网55 右旋字符串

今日任务：

1. LeetCode454 四数相加 Ⅱ
2. LeetCode383 赎金信
3. LeetCode15 三数之和
4. LeetCode18 四数之和



> ~~今日~~心情：终于找机会补回来了。

资料来源：

1. [代码随想录 | LeetCode454 四数相加 Ⅱ](https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
2. [代码随想录 | LeetCode383 赎金信](https://programmercarl.com/0383.%E8%B5%8E%E9%87%91%E4%BF%A1.html)
3. [代码随想录 | LeetCode15 三数之和](https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
4. [代码随想录 | LeetCode18 四数之和](https://programmercarl.com/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)

### 1 LeetCode454 四数相加 Ⅱ

:::info{title="题目"}
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
 

示例 1：
```
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
```
示例 2：
```
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1
```

  提示：

- n == nums1.length
- n == nums2.length
- n == nums3.length
- n == nums4.length
- 1 <= n <= 200
- -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

:::

四个元组分成两组，一组确定需要什么数字，另一组去匹配这个数字，这个过程就需要哈希表。注意这里只是查有多少，而不是具体把它们都找出来。

``` python
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        test_dict = {}
        for i in nums1:
            for j in nums2:
                if i + j in test_dict.keys():
                    test_dict[i + j] += 1
                else:
                    test_dict[i + j] = 1
        count = 0
        for i in nums3:
            for j in nums4:
                if -(i + j) in test_dict.keys():
                    count += test_dict[-(i + j)]
        return count
```

### 2 LeetCode383 赎金信

:::info{title="题目"}
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

 

示例 1：
```
输入：ransomNote = "a", magazine = "b"
输出：false
```
示例 2：
```
输入：ransomNote = "aa", magazine = "ab"
输出：false
```
示例 3：
```
输入：ransomNote = "aa", magazine = "aab"
输出：true
```

提示：

- 1 <= ransomNote.length, magazine.length <= 105
- ransomNote 和 magazine 由小写英文字母组成
:::

两个字符匹配嘛，这个哈希表最擅长了，键存字符，值存数字。

``` python
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        test_dict = {}
        for i in magazine:
            if i in test_dict:
                test_dict[i] += 1
            else:
                test_dict[i] = 1
        for i in ransomNote:
            if i not in test_dict:
                return False
            elif test_dict[i] == 0:
                return False
            else:
                test_dict[i] -= 1
        return True
```

### 3 LeetCode15 三数之和

> 内心OS：不愧是梦破碎的地方。

:::info{title="题目"}
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

 

示例 1：
```
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
```
示例 2：
```
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
```
示例 3：
```
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
```

提示：

- 3 <= nums.length <= 3000
- -105 <= nums[i] <= 105
:::

如果只是找哪三个数的和是0的话，还不至于被称为“梦破碎的地方”。主要是这个去重得好好想一下。去重使得使用哈希表来解成本太高了，还是双指针好一些。

先对这个数组进行排序，然后循环，每次循环设置从这次循环的位置到结尾的双指针，两个指针指向的数字再加一个循环的数字加起来验证是不是0。如果是0就存起来，如果大于0则移动右指针，如果小于0则移动左指针。

去重分为两个部分，一个部分是针对循环的，如果这次循环的数字和上次一致，就没有必要再双指针找了，因为只会找出一模一样的组合；另一个部分是针对发现三数组合存起来之后，两个指针必须要移动到和之前指的数字不同的位置，否则还是一模一样的组合。

还有两点，一个是判断大于0或者小于0之后没有必要再查重了，既然已经判断相加不能为0了，那左右都是移动，在`while right < left`里慢慢移动就好；另一个是我没写的，在对数组进行排序之后可以直接判断，如果数组开头就大于0的话就没有必要看了，最小的数都是正数还怎么加起来等于0。

:::warning{title="注意"}
我写的代码把right和left写反了，right实际上是左侧指针，left实际上是右侧指针。
:::

``` python
from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort()

        for i in range(len(nums) - 1):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            right = i + 1
            left = len(nums) - 1
            while right < left:
                if nums[i] + nums[right] + nums[left] == 0:
                    result.append([nums[i], nums[right], nums[left]])
                    # 只有在这里才有对left和right去重的意义
                    while right < left and nums[right] == nums[right + 1]:
                        right += 1
                    while right < left and nums[left] == nums[left - 1]:
                        left -= 1
                    right += 1
                    left -= 1
                elif nums[i] + nums[right] + nums[left] > 0:
                    left -= 1
                elif nums[i] + nums[right] + nums[left] < 0:
                    right += 1

        return result
```       

### 4 LeetCode18 四数之和

:::info{title="题目"}
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

示例 1：
```
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
```
示例 2：
```
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
```

提示：

- 1 <= nums.length <= 200
- -109 <= nums[i] <= 109
- -109 <= target <= 109
:::

这题思路和上一题是一样的，只是多了一层循环，也要考虑一开始的剪枝条件的变化和对第二层循环的处理。

``` python
from typing import List

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        result = []
        # 新的剪枝条件 不能再判断数组第一个元素大于或小于target了
        if target < 0 < nums[0]:
            return result
        if nums[len(nums) - 1] < 0 < target:
            return result

        for i in range(len(nums) - 1):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 注意是从i + 1开始循环
            for j in range(i + 1, len(nums) - 1):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                left = j + 1
                right = len(nums) - 1
                while left < right:
                    if nums[i] + nums[j] + nums[left] + nums[right] == target:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        while left < right and nums[left] == nums[left + 1]:
                            left += 1
                        while left < right and nums[right] == nums[right - 1]:
                            right -= 1
                        left += 1
                        right -= 1
                    elif nums[i] + nums[j] + nums[left] + nums[right] < target:
                        left += 1
                    else:
                        right -= 1

        return result
```

代码随想录算法训练营第七天 | LeetCode454 四数相加 Ⅱ、LeetCode383 赎金信、LeetCode15 三数之和、LeetCode18 四数之和

### 1 配置Nginx Proxy Manager并启动

随便哪里新建一个文件夹，在文件夹下新建`docker-compose.yml`配置文件，并且编辑文件：

```
version: '3'
services:
  app:
    image: 'jc21/nginx-proxy-manager:latest'
    restart: unless-stopped
    ports:
      - '80:80'              # 不建议修改端口
      - '81:81'              # 可以把冒号左边的 81 端口修改成你服务器上没有被占用的端口
      - '443:443'            # 不建议修改端口
    volumes:
      - ./data:/data         # 点号表示当前文件夹，冒号左边的意思是在当前文件夹下创建一个 data 目录，用于存放数据，如果不存在的话，会自动创建
      - ./letsencrypt:/etc/letsencrypt  # 点号表示当前文件夹，冒号左边的意思是在当前文件夹下创建一个 letsencrypt 目录，用于存放证书，如果不存在的话，会自动创建
```

之后在这个文件夹所在位置启动终端，输入以下命令以启动Nginx Proxy Manager：

```
docker-compose up -d     # -d 表示后台运行
```

之后访问81端口（我的镜像是19327端口）即可打开Nginx Proxy Manager的页面。

![image.png](https://www.misaka19327.cc/static/img/bb81fbae4c9bb2fc44ae442f1e7b8180.image.png)

### 2 配置Halo并启动

和配置Nginx Proxy Manager一个步骤：

``` 
version: "3"

services:
  halo:
    image: halohub/halo:2.13
    container_name: halo
    restart: on-failure:3
    depends_on:
      halodb:
        condition: service_healthy
    networks:
      halo_network:
    volumes:
      - ./halo2:/root/.halo2
    ports:
      - "8090:8090"
    healthcheck:
      test: ["CMD", "curl", "-f", "http://localhost:8090/actuator/health/readiness"]
      interval: 30s
      timeout: 5s
      retries: 5
      start_period: 30s
    command:
      - --spring.r2dbc.url=r2dbc:pool:mysql://halodb:3306/halo
      - --spring.r2dbc.username=root
      # MySQL 的密码，请保证与下方 MYSQL_ROOT_PASSWORD 的变量值一致。
      - --spring.r2dbc.password=o#DwN&JSa56
      - --spring.sql.init.platform=mysql
      # 外部访问地址，请根据实际需要修改
      - --halo.external-url=http://localhost:8090/

  halodb:
    image: mysql:8.1.0
    container_name: halodb
    restart: on-failure:3
    networks:
      halo_network:
    command: 
      - --default-authentication-plugin=caching_sha2_password
      - --character-set-server=utf8mb4
      - --collation-server=utf8mb4_general_ci
      - --explicit_defaults_for_timestamp=true
    volumes:
      - ./mysql:/var/lib/mysql
      - ./mysqlBackup:/data/mysqlBackup
    ports:
      - "3306:3306"
    healthcheck:
      test: ["CMD", "mysqladmin", "ping", "-h", "127.0.0.1", "--silent"]
      interval: 3s
      retries: 5
      start_period: 30s
    environment:
      # 请修改此密码，并对应修改上方 Halo 服务的 SPRING_R2DBC_PASSWORD 变量值
      - MYSQL_ROOT_PASSWORD=o#DwN&JSa56
      - MYSQL_DATABASE=halo

networks:
  halo_network:
```

```
docker-compose up -d
docker-compose logs -f // 查看实时日志
```

### 3 Nginx Proxy Manager配置反向代理

先把CloudFlare的CDN加速关掉。

![image.png](https://www.misaka19327.cc/static/img/3829468f1b58bc5bdcb67bde5918f655.image.png)

如果使用了docker容器，则使用`ip addr show docker0`查看在容器里的IP。

![image.png](https://www.misaka19327.cc/static/img/d4dbb67968c3b9982dbc6756c11a8f4d.image.png)

如图，Domain Name写域名，Scheme是协议不用管，Forward HostName/IP写127.0.0.1或者写刚才看的在docker容器里的IP，Forward Port写运行的服务所占用的端口（Halo默认8090）。Cache Assets是缓存，Block Common Exploits是阻止常见漏洞，Websockets Support是WebSocket接口支持，都可以打开。Access List是访问控制列表，不用管。

如果想要https访问（前提是域名已经解析到Nginx Proxy Manager所在的机器IP上），看下图：

![image.png](https://www.misaka19327.cc/static/img/44d8caeffec93ff7bcc3fb1d07c51333.image.png)

![image.png](https://www.misaka19327.cc/static/img/1ea03830d5d92b8b9cc01050aaf1bc54.image.png)

选中Force SSL，其他四个不用管，点Save，理论上就申请好了。

最终配置完成应该长这样：

![image.png](https://www.misaka19327.cc/static/img/8d272085f1505c02f57a406f0787367e.image.png)

配置Halo相关信息

今日任务：

1. 哈希表理论基础
2. LeetCode242 有效的字母异位词
3. LeetCode349 两个数组的交集
4. LeetCode202 快乐数
5. LeetCode1 两数之和



资料来源：

1. [代码随想录 | 哈希表理论基础](https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E5%93%88%E5%B8%8C%E8%A1%A8)
2. [代码随想录 | LeetCode242 有效的字母异位词](https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
3. [代码随想录 | LeetCode349 两个数组的交集](https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
4. [代码随想录 | LeetCode202 快乐数](https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html#%E6%80%9D%E8%B7%AF)
5. [代码随想录 | LeetCode1 两数之和](https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)

### 1 哈希表理论基础

#### 1.1 `dict`的底层原理

python3.5版本及之前的所有版本里，`dict`的底层是由二维数组构成的，每个数组中存放的是键的哈希值，键和值。每次取值时，先求出键的哈希值，然后取余得到数组下标，从而得到键所对应的值。其在内存中大体是这样的：

``` python
my_dict['name'] = 'jkc'
 
'''
此时的内存示意图
[
  [---, ---, ---],
  [---, ---, ---],
  [---, ---, ---],
  [---, ---, ---],
  [---, ---, ---],
  [1278649844881305901, 指向name的指针, 指向jkc的指针],
  [---, ---, ---],
  [---, ---, ---]
]
'''
```

:::tip{title="提示"}
python的哈希函数`hash()`和常规的哈希函数不太一样，它的哈希函数只能保证一个值在每个运行时内所对应的哈希值是相同的。一旦不在一个运行时里，得到的哈希值就可能不同。

![image.png](https://www.misaka19327.cc/static/img/ad83ea5196bc5a102770f0fd598981ba.image.png)
:::

这种存储方式也会带来一些弊端，比如说遍历字典的结果顺序不一定就是添加顺序，因为遍历字典本质上还是遍历那个二维数组而已，而那个二维数组的顺序只取决于键的哈希值。

在python3.6版本之后，字典的底层由一个二维数组和一个一维数组组成。每次在存入值时，还是先对键取哈希值然后取余，之后取余的结果对应一维数组的位置，一维数组中存储着这个键值对在二维数组中的位置，二维数组中存储键的哈希值，键和值。其在内存中大概是这样的：

``` python
my_dict['name'] = 'jkc'
my_dict['address'] = 'xxx'
my_dict['salary'] = 999999
 
'''
此时的内存示意图
indices = [1, 0, None, None, None, None, 2, None]
 
entries = [
  [-5954193068542476671, 指向name的指针, 执行jkc的指针],
  [9043074951938101872, 指向address的指针，指向xxx的指针],
  [7324055671294268046, 指向salary的指针, 指向999999的指针]
]
'''
```

这样就避免了之前版本中加元素顺序和遍历顺序不同的问题，并且空间上可以小很多，因为之前的版本的字典必须生成足够大的二维数组来存储键值对（即在之前的版本，即使只是初始化字典，也已经有了8\*3大小的二维数组）。

来源：[python进阶（24）Python字典的底层原理以及字典效率](https://www.cnblogs.com/jiakecong/p/15881370.html)

#### 1.2 `set`的底层原理

python的集合的底层是由哈希表构成的。向一个集合中插入元素的过程，就是向哈希表插入元素的过程。只是如果插入的位置已经有元素的话，python会比较它们俩的值（`__eq__()`）和哈希值（`__hash__()`）来确定它们是否一致，一致就是重复元素，不一致就是哈希碰撞。同理，查找元素时如果哈希值对应的位置有值，先比较值，值不同的话就是哈希碰撞。删除元素时，python也会按照这个顺序找元素，找到之后会赋一个特殊的值，等到下次集合调整大小时再删除。

#### 1.3 `dict`和`set`的操作

1. `dict`
- 初始化：`a = {}`或`a = dict()`
- 添加或修改元素：`a[i] = j`
- 删除并且返回被删除键对应的值：`a.pop(i)`
- 访问元素，如果键不存在则返回默认值：`a.get(key, defaultValue)`
- 清空字典：`a.clear()`
- 以列表形式返回可遍历的(key, value)元组类型数组：`a.items()`（具有类似效果的，但是只返回键或值的：`a.keys()``a.values()`）
2. `set`
- 初始化：`a = set()`
- 添加元素：`a.add(i)`
- 删除元素：`a.discard(i)`（该方法在i不存在于a时不会报错，会报错的版本是`a.delete(i)`）
- 清空集合：`a.clear()`

### 2 LeetCode242 有效的字母异位词

:::info{title="题目"}
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:
```
输入: s = "anagram", t = "nagaram"
输出: true
```
示例 2:
```
输入: s = "rat", t = "car"
输出: false
```

提示:

* 1 <= s.length, t.length <= 5 * 104
* s 和 t 仅包含小写字母
:::

``` python
# 我的代码
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s_map = {}
        t_map = {}
        for i in s:
            if i in s_map:
                s_map[i] += 1
            else:
                s_map[i] = 1
        for i in t:
            if i in t_map:
                t_map[i] += 1
            else:
                t_map[i] = 1
        if len(s_map) < len(t_map):
            temp = s_map
            s_map = t_map
            t_map = temp
        for char, num in s_map.items():
            if char not in t_map:
                return False
            else:
                if t_map[char] != num:
                    return False
        return True
``` 

这里直接用数组就好，因为说到底要查的东西总共就26种，没必要上哈希表了。

``` python
# 使用更少内存的一种写法
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record = [0] * 26
        for i in s:
            record[ord(i) - ord('a')] += 1
        for i in t:
            record[ord(i) - ord('a')] -= 1
        for i in record:
            if i != 0:
                return False
        return True
```

### 3 LeetCode349 两个数组的交集

:::info{title="题目"}
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：
```
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
```
示例 2：
```
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
```

提示：

* 1 <= nums1.length, nums2.length <= 1000
* 0 <= nums1[i], nums2[i] <= 1000
:::

先用`set`去重，然后再和另一个数组进行比较，比较的结果就是交集了。

``` python
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set_nums1 = set()
        return_list = []
        for i in nums1:
            set_nums1.add(i)
        for i in nums2:
            if i in set_nums1:
                return_list.append(i)
                set_nums1.discard(i)
        return return_list
```

### 4 LeetCode202 快乐数

:::info{title="题目"}
编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：
```
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
```
示例 2：
```
输入：n = 2
输出：false
```

提示：

* 1 <= n <= 231 - 1
:::

一定要注意，**当遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法**。这题就是用`set`去暴力解。

``` python
class Solution:
    def isHappy(self, n: int) -> bool:
        test_set = set()
        sum = n
        while True:
            n_str = str(sum)
            sum = 0
            for i in n_str:
                sum += int(i) * int(i)
            if sum == 1:
                return True
            if sum in test_set:
                return False
            else:
                test_set.add(sum)
```          

### 5 LeetCode1 两数之和

:::info{title="题目"}
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

 

示例 1：
```
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
```
示例 2：
```
输入：nums = [3,2,4], target = 6
输出：[1,2]
```
示例 3：
```
输入：nums = [3,3], target = 6
输出：[0,1]
```

提示：

* 2 <= nums.length <= 104
* -109 <= nums[i] <= 109
* -109 <= target <= 109
* 只会存在一个有效答案
:::

主要是想明白这个`map`要存的是谁，要找的是谁。

``` python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        test_map = {}
        for i in range(len(nums)):
            if (target - nums[i]) not in test_map.keys():
                test_map[nums[i]] = i
            else:
                return [i, test_map[target - nums[i]]]
```