leetcode 学习

### leetcode 学习知识点概览 #### 1. 两数之和 **暴力解法**：遍历数组中的每一个元素，对于每个元素 `nums[i]`，再遍历剩下的元素 `nums[j]`（其中 `j > i`），检查是否存在 `nums[i] + nums[j] == target` 的情况。这种方法的时间复杂度为 O(n^2)。 **哈希表解法**：遍历数组，对于每个元素 `nums[i]`，计算 `target - nums[i]`，并检查该差值是否已经存在于哈希表中。如果存在，则找到了答案；否则将 `nums[i]` 和它的索引添加到哈希表中。这种方法的时间复杂度为 O(n)，空间复杂度也为 O(n)。 #### 2. 两数相加 给定两个非空的链表，代表两个非负的整数。数字以逆序方式存储，每一位节点包含一个数字。将这两个数字相加并以相同形式返回结果。 - **链表结构**：使用 `ListNode` 类型表示链表，其中包含 `val`、`next` 两个字段。 - **实现细节**：定义一个名为 `head` 的指针用于移动，以及一个名为 `carry` 的变量表示进位。遍历两个链表，进行逐位相加，并处理进位问题。 - **注意事项**：初始化时，需要建立一个哑节点（dummy node）以方便操作链表，最终返回 `head.next` 即可。 #### 3. 解归并排序之两数组合并 合并两个已排序的数组，找到中值。 - **合并方法**：通过比较两个数组的元素，将较小的元素放入新的数组中，直到一个数组为空，然后将另一个数组剩余的元素全部加入新数组。 - **时间复杂度**：O(m+n)，其中 m 和 n 分别为两个数组的长度。 - **寻找中值**：合并后的数组为有序数组，可以直接从中找到中值。 #### 4. 最大容器盛水问题 给定一系列高度不等的垂直线，找出两根线组成的容器可以盛放的最大水量。 - **双指针法**：使用两个指针分别指向数组的两端，计算两个端点围成的矩形面积，移动高度较低的指针以尝试获取更大的面积。 - **关键理解**：为了得到最大面积，需要移动高度较小的一侧，这是因为移动高度较高的一侧会导致宽度减小而无法获得更大面积。 #### 5. 删除链表的倒数第 N 个结点 - **方法一**：先遍历一遍链表以确定链表长度，再根据长度找到倒数第 N 个结点的前一个结点，删除目标结点。 - **方法二**：使用快慢指针技巧。定义两个指针 `slow` 和 `fast`，初始时 `fast` 指针先前进 N 步，然后两个指针同时前进。当 `fast` 指针到达链表尾部时，`slow` 指针指向倒数第 N 个结点的前一个结点，此时可以直接删除目标结点。 #### 6. 二分查找法 在有序数组中查找特定元素的第一个位置或最后一个位置。 - **查找第一个位置**：使用二分查找定位特定元素的第一个出现位置。 - **查找最后一个位置**：使用二分查找定位特定元素的最后一个出现位置。 - **实现细节**：通过维护两个指针 `left` 和 `right`，逐步缩小搜索范围，直至找到目标位置或确定不存在。 #### 7. 合并区间 给定一系列可能重叠的区间，将所有重叠的区间合并。 - **排序**：首先对输入的区间按照起始点排序。 - **合并过程**：遍历排序后的区间列表，对于每个新区间，检查它是否与当前结果列表中的最后一个区间重叠。如果重叠，则更新结果列表中最后一个区间的结束点；如果不重叠，则将新区间添加到结果列表中。 以上是针对给定的 leetcode 学习知识点的具体解析，希望能够帮助理解和掌握这些基础算法和数据结构的概念与实现细节。