LRU 缓存的核心思想是淘汰最长时间未被访问的数据。为了实现高效的查找、插入和删除操作，我们通常结合使用两种数据结构：一个双向链表和一个哈希表（或字典）。

1. 数据结构选择

双向链表用于维护数据项的被访问顺序。最近被访问的节点放在链表头部（或尾部），而最久未被访问的节点自然会被挤到链表尾部（或头部），这样当需要淘汰数据时，直接删除链表尾部的节点即可。使用双向链表的原因是在删除任意节点时，可以在 O(1) 时间内完成，前提是已经找到了该节点。

哈希表则通过缓存数据的键来映射到双向链表中对应的节点。这样，我们可以在 O(1) 时间内通过键找到对应的节点。

2. 节点设计

链表的每个节点应该包含三个部分：键、值以及指向前后节点的指针。键的存在是为了当需要淘汰链表尾部的节点时，我们可以通过节点中的键来删除哈希表中对应的项。

3. 主要操作

获取数据（get操作）： 首先检查哈希表中是否存在该键。如果不存在，返回空或特定标识（如-1）。如果存在，则根据哈希表定位到链表中对应的节点。然后，将该节点从当前位置删除，并重新插入到链表头部。最后返回节点的值。这个移动节点的操作是为了更新该数据的访问顺序，将其标记为最近使用。

插入数据（put操作）： 首先检查哈希表中是否已存在该键。如果存在，则更新对应节点的值，然后将该节点移动到链表头部（类似于get操作中的移动）。如果不存在，则需要新建一个节点，并将其添加到链表头部。同时，将键和该节点添加到哈希表中。之后，检查缓存是否已超过容量。如果超过，则需要删除链表尾部的节点（即最久未使用的节点），并在哈希表中删除对应的键。

4. 辅助操作

为了保持代码清晰，通常会抽象出几个辅助函数，例如：将节点添加到链表头部、移除特定节点、移除尾部节点并返回该节点等。

5. 复杂度分析

由于哈希表的查找、插入和删除操作的平均时间复杂度为 O(1)，而双向链表的插入、删除（在已知节点指针的情况下）操作的时间复杂度也是 O(1)，因此整个 LRU 缓存的 get 和 put 操作的时间复杂度都是 O(1)。空间复杂度是 O(n)，其中 n 是缓存的容量。

6. 简单代码框架（以伪代码形式描述）

首先定义链表节点类，包含 key, value, prev, next。

然后定义 LRUCache 类，包含以下成员：

• 一个哈希表（用于存储键到节点的映射）

• 两个哑节点（dummy head 和 dummy tail，用于简化链表边界操作）

• 容量变量

在构造函数中初始化哈希表、容量以及连接两个哑节点。

实现 get 方法：如果键在哈希表中，定位节点，移除它并将其添加到头部，返回值；否则返回-1。

实现 put 方法：如果键存在，更新值，移动节点到头部。如果不存在，创建新节点，添加到头部和哈希表。如果超容，删除尾部节点（同时删除哈希表中对应键）。

私有辅助方法可能包括：

• 将节点移动到头部（先移除再头部添加）

• 移除节点（从链表中解除链接）

• 在头部添加节点

• 移除尾部节点并返回该节点（以便获取其键）

通过以上设计和步骤，就可以实现一个高效的 LRU 缓存机制。

环形缓冲区是一种数据结构，它使用一个固定大小的数组和两个指针（或索引）来模拟一个首尾相连的循环空间。它非常适合作为先进先出（FIFO）的缓冲区，尤其在数据生产者（Producer）和消费者（Consumer）速度不一致时，能高效地利用预分配的内存。

核心设计要素

1. 底层存储 (Underlying Storage)：使用一个固定大小的数组（在C++中可能是std::vector，在C中是原生数组，在Java中是array等）来存储元素。

2. 容量 (Capacity)：数组的固定大小，即缓冲区最多能容纳的元素数量。

3. 写指针/索引 (Write Pointer/Index)：指向下一个可写入数据的位置。

4. 读指针/索引 (Read Pointer/Index)：指向下一个可读取数据的位置。

5. 缓冲区状态：通常我们需要知道缓冲区是空还是满，因为读指针和写指针重合时可能代表这两种状态。

关键操作与算法

1. 初始化 (Initialization)

   • 分配一个大小为capacity的数组。

   • 将读指针 (read_idx 或 head) 和写指针 (write_idx 或 tail) 都初始化为 0（或其他相同的值）。

   • 此时缓冲区为空。

2. 写入数据 (Write / Push / Enqueue)

   • 检查缓冲区是否已满：这是最关键的一步。如果缓冲区已满，根据需求决定是覆盖最旧的数据（覆盖模式）还是拒绝写入（非覆盖模式）。

     • 判断满的条件：(write_idx + 1) % capacity == read_idx（这是一种常见的策略，会浪费一个数组位置来区分空和满的状态）。另一种方法是维护一个计数器记录元素数量。

   • 如果未满（或有空间），将数据放入write_idx指向的位置。

   • 更新写指针：write_idx = (write_idx + 1) % capacity。取模操作是实现“环形”的关键，它让指针在到达数组末尾后能回到开头。

3. 读取数据 (Read / Pop / Dequeue)

   • 检查缓冲区是否为空：read_idx == write_idx。

   • 如果不为空，从read_idx指向的位置取出数据。

   • 更新读指针：read_idx = (read_idx + 1) % capacity。

4. 检查空 (Is Empty)

   • 条件：read_idx == write_idx。

5. 检查满 (Is Full)

   • 条件（使用预留空间法）：(write_idx + 1) % capacity == read_idx。

   • 这种方法会使得缓冲区最多容纳capacity - 1个元素，用一个位置的空闲来明确区分空和满的状态，简化逻辑。

6. 获取当前元素数量 (Size)

   • 计算：(write_idx - read_idx + capacity) % capacity。

   • 如果写指针在读指针之后，直接相减。如果写指针绕回了读指针前面（由于环形），相减会是负数，加上capacity再取模就能得到正确的结果。

设计考量与变体

1. 线程安全 (Thread Safety)：

   • 如果生产者和消费者运行在不同的线程，对缓冲区的操作必须是原子的或需要加锁（互斥锁，Mutex）。

   • 通常采用一个锁来保护整个缓冲区，或者在无锁编程中精心设计原子操作（更复杂）。

2. 覆盖 vs 非覆盖 (Overwrite vs Non-overwrite)：

   • 非覆盖模式：当缓冲区满时，拒绝写入或返回错误。适合不能丢失旧数据的场景。

   • 覆盖模式：当缓冲区满时，写入新数据并自动移动读指针（即覆盖最旧的数据）。适合只关心最新数据的场景（如实时音频流）。

3. 内存管理：

   • 如果存储的是对象（而非基本数据类型），在覆盖或弹出时需要正确调用析构函数。

   • 在C++等语言中，可以使用std::vector来管理内存，但需要注意对象的构造和析构。

4. 批量操作：

   • 为了提高效率，可以实现批量写入（push_n）和批量读取（pop_n）的功能，减少边界检查和指针更新的次数。

简单代码框架（C++风格伪代码）

class CircularBuffer {
public:
    CircularBuffer(int capacity) : capacity_(capacity + 1) { // 多分配一个空间用于区分空满
        buffer_.resize(capacity_);
        read_idx_ = 0;
        write_idx_ = 0;
    }

    bool push(const T& item) {
        if (isFull()) {
            return false; // 非覆盖模式，满了就失败
        }
        buffer_[write_idx_] = item;
        write_idx_ = (write_idx_ + 1) % capacity_;
        return true;
    }

    bool pop(T& item) {
        if (isEmpty()) {
            return false;
        }
        item = buffer_[read_idx_];
        read_idx_ = (read_idx_ + 1) % capacity_;
        return true;
    }

    bool isEmpty() const {
        return read_idx_ == write_idx_;
    }

    bool isFull() const {
        return (write_idx_ + 1) % capacity_ == read_idx_;
    }

    size_t size() const {
        return (write_idx_ - read_idx_ + capacity_) % capacity_;
    }

private:
    std::vector<T> buffer_;
    size_t capacity_; // 实际数组大小，为期望容量+1
    size_t read_idx_;
    size_t write_idx_;
};

总结

设计一个环形缓冲区的核心在于：

• 使用一个固定大小的数组和两个指针。

• 通过取模运算实现指针的循环。

• 精心设计判断“空”和“满”的条件（通常使用预留一个空位的方法）。

• 根据应用场景决定覆盖策略和线程安全需求。

这个设计在系统编程、嵌入式开发、数据流处理和高性能计算中非常常见且实用。

最小堆是一种特殊的完全二叉树，它满足每个节点的值都小于或等于其子节点的值。这意味着堆的根节点始终是整个堆中的最小元素。

核心操作与实现步骤：

1. 堆的表示我们通常使用一个数组（或列表）来表示堆。对于一个给定索引 i 的节点：

• 其父节点的索引为 (i - 1) // 2

• 其左子节点的索引为 2 * i + 1

• 其右子节点的索引为 2 * i + 2

2. 关键辅助方法：上浮（Heapify Up）当一个新元素被添加到堆的末尾时，可能会破坏堆的性质。上浮操作通过将新元素与其父节点进行比较和交换，使其“上浮”到正确的位置，从而恢复堆的性质。

• 具体步骤：比较当前节点与其父节点的值。如果当前节点的值更小，则交换它们。重复这个过程，直到当前节点不再小于其父节点，或者到达了根节点。

3. 关键辅助方法：下沉（Heapify Down）当移除根节点（最小元素）后，我们将堆的最后一个元素移动到根位置，这可能会破坏堆的性质。下沉操作通过将根元素与其较小的子节点进行比较和交换，使其“下沉”到正确的位置，从而恢复堆的性质。

• 具体步骤：比较当前节点与其左右子节点的值。找到值最小的那个子节点。如果当前节点的值大于这个最小子节点的值，则交换它们。重复这个过程，直到当前节点不再大于其子节点，或者到达了叶子节点。

4. 主要操作实现：

• 插入（Insert / Push）：

  1. 将新元素添加到数组的末尾。

  2. 对这个新元素执行上浮操作。

• 提取最小值（Extract Min / Pop）：

  1. 检查堆是否为空。如果为空，则报错或返回空值。

  2. 存储根节点的值（即最小值）以备返回。

  3. 将数组的最后一个元素移动到根节点的位置，并删除最后一个元素。

  4. 对新的根节点执行下沉操作。

  5. 返回之前存储的最小值。

• 查看最小值（Peek）：

  1. 检查堆是否为空。

  2. 直接返回根节点的值（array[0]）。

• 构建堆（Heapify）： 从一个无序数组构建堆，一个高效的方法是从最后一个非叶子节点开始，倒序对每个节点执行下沉操作。最后一个非叶子节点的索引是 (n // 2) - 1（n为数组长度）。

代码实现示例（Python）：

class MinHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2

    def left_child(self, i):
        return 2 * i + 1

    def right_child(self, i):
        return 2 * i + 2

    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def insert(self, key):
        # 1. 将新元素添加到末尾
        self.heap.append(key)
        # 2. 获取新元素的索引并执行上浮
        index = len(self.heap) - 1
        self._heapify_up(index)

    def _heapify_up(self, index):
        # 当不是根节点且当前节点值小于父节点值时，继续上浮
        while index > 0 and self.heap[index] < self.heap[self.parent(index)]:
            parent_index = self.parent(index)
            self.swap(index, parent_index)
            index = parent_index # 更新当前位置为父节点位置

    def extract_min(self):
        if not self.heap:
            return None
        
        # 1. 保存最小值
        min_val = self.heap[0]
        last_val = self.heap.pop() # 移除并返回最后一个元素

        # 2. 如果堆中还有元素，将最后一个元素放到根节点并下沉
        if self.heap:
            self.heap[0] = last_val
            self._heapify_down(0)
        
        # 3. 返回最小值
        return min_val

    def _heapify_down(self, index):
        smallest = index
        left = self.left_child(index)
        right = self.right_child(index)
        size = len(self.heap)

        # 找出当前节点、左子节点、右子节点三者中的最小值
        if left < size and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < size and self.heap[right] < self.heap[smallest]:
            smallest = right

        # 如果最小值不是当前节点，则交换并继续下沉
        if smallest != index:
            self.swap(index, smallest)
            self._heapify_down(smallest) # 递归下沉

    def peek(self):
        return self.heap[0] if self.heap else None

# 使用示例
min_heap = MinHeap()
min_heap.insert(5)
min_heap.insert(3)
min_heap.insert(8)
min_heap.insert(1)
min_heap.insert(2)

print(min_heap.extract_min()) # 输出: 1
print(min_heap.extract_min()) # 输出: 2
print(min_heap.peek())        # 输出: 3

总结：实现最小堆的核心在于维护堆的性质，这主要通过上浮（用于插入）和下沉（用于提取）两个操作来完成。使用数组存储可以高效地利用完全二叉树的特性，通过简单的索引计算即可访问任何节点的父节点和子节点。

最大堆是一种特殊的完全二叉树，它满足每个节点的值都大于或等于其子节点的值。这意味着堆的根节点始终是整个堆中的最大元素。

实现最大堆的核心在于两个基本操作：insert（插入）和extractMax（提取最大值）。为了维护堆的性质，我们还需要一个关键的内部方法：heapifyUp（向上调整）和heapifyDown（向下调整）。

1. 数据结构选择我们通常使用数组来表示堆，因为堆是一个完全二叉树，数组的存储非常高效且节省空间。对于数组中任意位置i的节点：

• 其父节点的索引为 Math.floor((i-1)/2)

• 其左子节点的索引为 2*i + 1

• 其右子节点的索引为 2*i + 2

2. 关键操作详解

插入操作 (insert):当向堆中插入一个新元素时，我们首先将其添加到数组的末尾（即完全二叉树的最后一个位置），这会暂时破坏堆的性质。然后通过heapifyUp操作将其调整到正确的位置。

向上调整 (heapifyUp):这个方法从新插入的节点开始，将其与父节点进行比较。如果当前节点的值大于其父节点的值，就交换它们的位置。这个过程持续进行，直到当前节点不再大于其父节点，或者已经到达根节点为止。

提取最大值操作 (extractMax):由于根节点就是最大值，我们首先取出根节点的值。然后，将数组的最后一个元素移动到根节点的位置（这同样会破坏堆的性质）。最后通过heapifyDown操作将新的根节点调整到正确的位置。

向下调整 (heapifyDown):这个方法从根节点开始，将其与左右子节点中较大的那个进行比较。如果当前节点的值小于那个较大的子节点，就交换它们的位置。这个过程持续进行，直到当前节点大于或等于其两个子节点，或者已经到达叶子节点为止。

3. 代码实现步骤

首先创建一个类MaxHeap，包含一个构造函数来初始化存储堆的数组。

实现insert方法：

• 将新元素推入数组末尾

• 调用heapifyUp方法，传入最后一个元素的索引

实现heapifyUp方法：

• 使用循环，不断比较当前节点与其父节点

• 如果当前节点值大于父节点值，则交换

• 将当前索引更新为父节点索引，继续向上比较

• 直到条件不满足或到达根节点

实现extractMax方法：

• 如果堆为空，返回null或抛出异常

• 存储根节点的值（最大值）

• 将最后一个元素移到根节点，并移除最后一个元素

• 如果堆不为空，调用heapifyDown方法从根节点开始调整

• 返回存储的最大值

实现heapifyDown方法：

• 从给定索引开始，假设该索引是最大值

• 找到左右子节点的索引

• 如果左子节点存在且大于当前节点，更新最大值索引

• 如果右子节点存在且大于当前最大值，更新最大值索引

• 如果最大值索引不是初始索引，交换位置并递归/迭代继续向下调整

4. 其他实用方法您还可以实现一些辅助方法：

• peek: 查看最大值而不移除

• size: 返回堆的大小

• isEmpty: 检查堆是否为空

• buildHeap: 从一个无序数组快速构建堆

5. 复杂度分析

• 插入操作: O(log n)

• 提取最大值: O(log n)

• 查看最大值: O(1)

• 构建堆: O(n)

这种数组表示加调整操作的实现方式既高效又直观，是实现最大堆的标准方法。

堆的插入操作（Insert）

向堆（以最小堆为例）中插入一个新元素，通常遵循以下步骤，其目标是维持堆的属性（即父节点的值总是小于或等于其子节点的值）。

第一步，将新元素添加到堆的末尾。为了保持堆是一棵完全二叉树，新元素必须被放置在最后一个可用的位置，也就是在数组表示法中数组的最后一个元素之后。

第二步，进行“上浮”（Percolate Up 或 Sift Up）操作。由于新元素被放在末尾，它可能会破坏堆的性质（例如，它可能比其父节点小）。因此，需要将它与其父节点进行比较。如果新元素的值小于其父节点的值，则交换它们的位置。重复这个比较和交换的过程，一直向上移动，直到新元素不再小于其父节点，或者它已经到达堆的根节点（即数组的索引0位置）为止。

这个过程确保了新元素被放置到满足堆性质的正确位置，同时整个堆的结构得以恢复。

堆的删除操作（Delete）

从堆中删除元素通常是指删除堆的根节点（因为堆常用于优先队列，根节点是优先级最高，即最小或最大的元素）。删除任意中间节点的情况较为复杂且不常见，如果需要，通常也是通过特殊处理实现，但标准操作是删除根节点。

删除根节点的步骤如下：

第一步，移除根节点。这将留下一个空位，破坏了堆的结构。

第二步，将堆的最后一个元素移动到根节点的空位。用最后一个元素填充根位置是为了保持完全二叉树的性质。

第三步，进行“下沉”（Percolate Down 或 Sift Down）操作。新的根元素很可能比它的子节点大（对于最小堆而言），因此需要调整以恢复堆性质。将新的根节点与其左右子节点中较小的那一个进行比较。如果根节点大于这个较小的子节点，则交换它们的位置。然后，继续以这个新位置为起点，重复这个过程：将节点与其当前子节点中较小的进行比较，并在需要时交换，直到该节点不再大于其子节点，或者它已经下沉到了叶子节点（即没有子节点了）为止。

通过这个下沉过程，根元素被逐步移动到其正确的位置，堆的性质得以恢复。

总结关键点

插入操作的核心是“上浮”，从底部开始向上调整，直到堆性质满足。 删除操作（特指删除根节点）的核心是“下沉”，从顶部开始向下调整，直到堆性质满足。 这两个操作的时间复杂度都是 O(log n)，其中 n 是堆中元素的数量，因为调整过程沿着树的高度进行。

Top K 问题通常分为两类：求最大/最小的 K 个元素。堆是解决这类问题的完美数据结构，因为它可以在不进行完全排序的情况下高效地获取极值。

核心思想是利用堆的特性来维护一个大小为 K 的“候选集”，从而将时间复杂度从 O(n log n) 降低到 O(n log K)。

一、两种场景与堆的选择

1. 求最大的 K 个元素 / 求前 K 高频率的元素

   • 使用最小堆（Min Heap）。

   • 思路：我们维护一个大小为 K 的最小堆。堆顶始终是当前候选集中最小的那个元素。遍历整个数组时，如果新元素比堆顶元素大，就替换掉堆顶（这个最小的元素），然后重新调整堆，让新的最小的元素浮到堆顶。这样，堆里始终保存着到目前为止遇到的最大的 K 个元素（堆顶是这K个里最小的，即门槛）。

   • 为什么是最小堆？ 因为我们的“门槛”在里面是最小的，任何比门槛大的新元素都有资格进入候选集，并踢掉当前的门槛。

2. 求最小的 K 个元素 / 求前 K 低频率的元素

   • 使用最大堆（Max Heap）。

   • 思路：与上述相反。维护一个大小为 K 的最大堆。堆顶是当前候选集中最大的那个元素。如果新元素比堆顶元素小，就替换掉堆顶（这个最大的元素），然后重新调整堆。这样，堆里始终保存着到目前为止遇到的最小的 K 个元素（堆顶是这K个里最大的，即门槛）。

   • 为什么是最大堆？ 因为我们的“门槛”在里面是最大的，任何比门槛小的新元素都有资格进入候选集，并踢掉当前的门槛。

二、算法步骤（以求最大的K个元素为例）

假设我们有一个数组，想找出其中最大的 K 个数。

1. 初始化：创建一个最小堆，并将其大小限制为 K。

2. 建堆：

   • 先将前 K 个元素直接加入堆中。

   • 此时，堆是一个包含了 K 个元素的最小堆。堆顶元素是这 K 个元素里最小的。

3. 遍历与调整：

   • 从第 K+1 个元素开始，遍历数组中剩余的所有元素。

   • 对于每个新元素 num，将其与堆顶元素进行比较。

   • 如果 num 大于堆顶元素，说明它有资格成为 Top K 的候选。此时，我们做两件事：

     • 弹出当前的堆顶元素（即丢弃当前候选集中最小的那个）。

     • 将新元素 num 加入堆中。

   • 如果 num 小于或等于堆顶元素，则直接跳过，因为它不可能比当前候选集中的任何一个元素大。

4. 获取结果：

   • 当数组全部遍历完毕后，堆中剩下的所有元素就是我们要找的最大的 K 个元素。

注意：最终堆内的元素是无序的。如果需要按顺序输出，可以逐个从堆中弹出元素（弹出的是当前最小的），弹出的顺序就是从小到大的顺序。如果希望从大到小，需要将弹出的结果反转。

三、复杂度分析

• 时间复杂度：O(n log K)

  • 建一个大小为 K 的堆：O(K)

  • 最坏情况下，我们需要遍历 n - K 个元素，并且每个元素都可能需要进行一次堆调整（插入或删除），堆调整的时间复杂度是 O(log K)。所以总时间是 O(K + (n - K) log K) ≈ O(n log K)。

  • 当 K 远小于 n 时，这比直接排序（O(n log n)）要高效得多。

• 空间复杂度：O(K)

  • 我们只需要维护一个大小为 K 的堆。

四、简单举例说明

假设数组是 [4, 1, 5, 2, 3]，求 Top 3（最大的3个元素）。我们使用最小堆。

1. 取前3个元素 [4, 1, 5] 建最小堆。堆结构为 [1, 4, 5]，堆顶是 1。

2. 遍历下一个元素 2：

   • 比较：2 > 1（堆顶），需要操作。

   • 弹出堆顶 1，加入 2。调整后的堆为 [2, 4, 5]，新堆顶是 2。

3. 遍历下一个元素 3：

   • 比较：3 > 2（堆顶），需要操作。

   • 弹出堆顶 2，加入 3。调整后的堆为 [3, 4, 5]，新堆顶是 3。

4. 遍历结束。堆中最后的元素 [3, 4, 5] 就是最大的 Top 3 元素。

总结

选择堆的类型是关键：求最大K用最小堆，求最小K用最大堆。算法核心是维护一个大小为K的堆作为动态候选集，通过不断与堆顶门槛值比较来更新候选集，最终高效地得到结果。这种方法在数据流或海量数据场景下尤其有用，因为它不需要将全部数据一次性加载到内存中。

1. 使用哈希表（或集合）遍历数组，将每个元素存入哈希表（或集合）。在插入前检查是否已存在，若存在则说明有重复。时间复杂度 O(n)，空间复杂度 O(n)。

示例代码（Python）：

def has_duplicate(arr):
    seen = set()
    for num in arr:
        if num in seen:
            return True
        seen.add(num)
    return False

2. 排序后比较相邻元素先对数组排序，然后遍历检查相邻元素是否相同。时间复杂度取决于排序算法（通常 O(n log n)），空间复杂度 O(1)（原地排序时）。

示例代码（Python）：

def has_duplicate(arr):
    arr.sort()
    for i in range(1, len(arr)):
        if arr[i] == arr[i-1]:
            return True
    return False

3. 使用语言内置函数某些语言提供快捷方法（如 Python 中比较集合与数组长度）：

def has_duplicate(arr):
    return len(arr) != len(set(arr))

选择建议：

• 若注重效率且可接受额外空间，首选哈希表方法。

• 若空间有限且可修改原数组，可用排序方法。

• 注意考虑输入数据类型（如是否支持哈希）和边界情况（如空数组）。

以上方法均能有效检测重复元素，具体可根据实际场景选择。

方法一：暴力枚举法

这是最直接的方法。使用两层循环来遍历所有可能的数对组合，检查它们的和是否等于目标值。

步骤：

1. 第一层循环从索引 i = 0 开始，遍历到数组的倒数第二个元素。

2. 第二层循环从索引 j = i + 1 开始，遍历到数组的最后一个元素。

3. 在循环内部，检查 nums[i] + nums[j] 是否等于 target。

4. 如果相等，则返回 [i, j] 或 [nums[i], nums[j]]（根据题目要求返回索引或数值）。

代码示例 (Python)：

def two_sum_brute_force(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j] # 返回索引
    return None # 如果没有找到，返回None

优缺点：

• 优点： 思路简单，易于理解和实现。

• 缺点： 时间复杂度为 O(n²)，当数组很大时效率非常低。

方法二：哈希表法（推荐）

这是一种利用空间换时间的高效方法。通过遍历数组，同时用一个哈希表（在Python中是字典）来记录已经遍历过的数字及其索引。

步骤：

1. 初始化一个空的字典 num_map。

2. 遍历数组，对于每一个数字 num，计算其与目标值的差值 complement = target - num。

3. 检查这个差值 complement 是否已经存在于字典 num_map 中。

   • 如果存在，说明我们找到了这两个数。直接返回当前数的索引和字典中存储的差值的索引 [num_map[complement], current_index]。

   • 如果不存在，则将当前数字 num 作为键，其索引 index 作为值，存入字典 num_map 中，以备后续查找。

代码示例 (Python)：

def two_sum_hash(nums, target):
    num_map = {} # 创建空字典，用于存储 {数值: 索引}
    for index, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            # 找到答案，返回之前存的 complement 的索引和当前索引
            return [num_map[complement], index]
        # 没找到，就把当前数字和它的索引存入字典
        num_map[num] = index
    return None # 如果没有找到，返回None

例子说明：假设 nums = [2, 7, 11, 15], target = 9

• 第一步：num=2, complement=7。7 不在字典中，将 {2: 0} 存入字典。

• 第二步：num=7, complement=2。2 在字典中（索引为0），立即返回 [0, 1]。

优缺点：

• 优点： 时间复杂度为 O(n)，只需遍历一次数组，效率极高。

• 缺点： 空间复杂度为 O(n)，需要额外的空间来存储哈希表。

方法三：双指针法（适用于已排序数组）

如果数组是已排序的，并且题目要求返回的是数值而不是索引，可以使用这种方法。

步骤：

1. 初始化两个指针，left 指向数组开头（索引0），right 指向数组末尾（最后一个索引）。

2. 循环条件为 left < right。

3. 计算两个指针指向的数字之和 current_sum = nums[left] + nums[right]。

4. 将 current_sum 与 target 比较：

   • 如果 current_sum == target，成功找到，返回 [nums[left], nums[right]]。

   • 如果 current_sum < target，说明和太小，需要将 left 指针向右移动（增大数值）。

   • 如果 current_sum > target，说明和太大，需要将 right 指针向左移动（减小数值）。

代码示例 (Python)：

# 注意：此方法要求数组已排序，且返回的是数值而非索引
def two_sum_two_pointers(sorted_nums, target):
    left, right = 0, len(sorted_nums) - 1
    while left < right:
        current_sum = sorted_nums[left] + sorted_nums[right]
        if current_sum == target:
            return [sorted_nums[left], sorted_nums[right]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return None

优缺点：

• 优点： 时间复杂度为 O(n)，空间复杂度为 O(1)（不需要额外空间）。

• 缺点： 要求输入数组必须是有序的。如果无序，先排序会破坏原始索引，因此不适用于需要返回原始索引的问题。

总结与推荐

• 通用且最高效的解法是哈希表法。它适用于未排序数组，并且能高效地返回索引。

• 如果数组已经排序，并且只需要返回值，双指针法是更优雅的选择。

• 暴力枚举法虽然简单，但在实际应用中应尽量避免，因为其性能较差。

方法一：排序 + 双指针法（最优解）

这是解决此问题最高效和常用的方法。

核心思想：

1. 排序：首先将数组进行排序。排序是后续使用双指针技巧的基础，并且能帮助我们轻松跳过重复的元组。

2. 固定一个数，转化为两数之和问题：遍历数组，将当前固定的数字 nums[i] 作为三元组的第一个元素。那么问题就转化为：在 i 之后的子数组中，寻找两个数，使得它们的和等于 -nums[i]（即 target = 0 - nums[i]）。

3. 双指针寻找两数之和：对于固定的 nums[i]，初始化两个指针：

   • left 指针指向 i+1（子数组的起始位置）。

   • right 指针指向数组的末尾 len(nums)-1。

4. 指针移动策略：

   • 计算 sum = nums[i] + nums[left] + nums[right]。

   • 如果 sum == 0，找到了一个有效三元组，将其加入结果列表。然后同时移动 left 和 right 指针（left++, right--），并跳过所有重复的值以避免得到重复的解。

   • 如果 sum < 0，说明总和太小，需要增大，因此将 left 指针右移（left++）。

   • 如果 sum > 0，说明总和太大，需要减小，因此将 right 指针左移（right--）。

5. 跳过重复值：在移动指针和遍历固定数时，都需要检查并跳过重复的数字，这是保证结果不重复的关键。

代码示例 (Python):

def three_sum(nums):
    nums.sort()  # 先排序
    result = []
    n = len(nums)
    
    for i in range(n - 2):  # 遍历到倒数第三个元素即可
        # 跳过重复的固定数
        if i > 0 and nums[i] == nums[i-1]:
            continue
            
        left, right = i + 1, n - 1
        target = -nums[i]  # 转化为两数之和问题
        
        while left < right:
            current_sum = nums[left] + nums[right]
            
            if current_sum == target:
                result.append([nums[i], nums[left], nums[right]])
                # 找到答案后，同时移动左右指针并跳过重复值
                left += 1
                right -= 1
                # 跳过左侧重复值
                while left < right and nums[left] == nums[left-1]:
                    left += 1
                # 跳过右侧重复值
                while left < right and nums[right] == nums[right+1]:
                    right -= 1
                    
            elif current_sum < target:
                left += 1
            else: # current_sum > target
                right -= 1
                
    return result

复杂度分析：

• 时间复杂度：O(N²)。排序的时间复杂度是 O(N log N)。外层循环遍历每个元素，内层双指针遍历每个元素，所以双指针部分的时间复杂度是 O(N) * O(N) = O(N²)。总复杂度由更高的 O(N²) 主导。

• 空间复杂度：O(1) 或 O(N)。这取决于排序算法的实现。通常来说，使用堆排序或快速排序的空间复杂度是 O(1)，而使用归并排序则是 O(N)。我们使用的额外空间（结果列表除外）是常数级别的。

方法二：使用哈希集合（两数之和的扩展）

这种方法思路直接，但需要注意去重的细节，且效率通常低于双指针法。

核心思想：

1. 对数组进行排序（主要用于方便去重）。

2. 外层循环固定第一个数 nums[i]。

3. 内层循环将问题转化为：在 i 之后的数组中，寻找两数之和为 -nums[i]。这个过程可以使用一个哈希集合 (seen) 来辅助。

4. 对于内层循环中的每个 nums[j]，计算需要的补数 complement = -nums[i] - nums[j]。

5. 检查这个补数是否已经存在于之前遍历时创建的哈希集合 seen 中。

   • 如果存在，说明找到了一个三元组 [nums[i], complement, nums[j]]。

   • 然后将 nums[j] 加入到 seen 中，为后续的查找做准备。

6. 同样，需要在多个层级跳过重复的值来避免重复解。

代码示例 (Python):

def three_sum_hash(nums):
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n):
        # 跳过重复的固定数
        if i > 0 and nums[i] == nums[i-1]:
            continue
            
        seen = set() # 为每个固定的nums[i]创建一个新的集合
        j = i + 1
        while j < n:
            complement = -nums[i] - nums[j]
            if complement in seen:
                result.append([nums[i], complement, nums[j]])
                # 找到一个解后，跳过后面所有重复的nums[j]
                while j + 1 < n and nums[j] == nums[j+1]:
                    j += 1
            seen.add(nums[j])
            j += 1
            
    return result

复杂度分析：

• 时间复杂度：O(N²)。外层循环 O(N)，内层循环也是 O(N)，所以是 O(N²)。哈希集合的插入和查询操作平均是 O(1)。

• 空间复杂度：O(N)。主要用于存储哈希集合，在最坏情况下可能需要存储几乎所有元素。

总结与推荐

强烈推荐使用第一种方法（排序 + 双指针）。原因如下：

1. 效率更高：虽然理论时间复杂度相同，但双指针法避免了哈希表的相关开销（计算哈希值、解决哈希冲突等），实际运行更快。

2. 空间更优：双指针法通常只需要常数级别的额外空间（不包括存储结果的空间）。

3. 逻辑清晰：排序后，利用数组的有序性来移动指针，逻辑非常直观和优雅。

第二种哈希法作为一种替代思路了解即可，在解决其扩展问题（如“两数之和”）时非常有用，但在此特定问题上并非最优选择。

要在数组中找到连续子数组的最大和，最常用且高效的方法是使用 Kadane 算法。该算法通过一次遍历数组即可解决问题，时间复杂度为 O(n)，空间复杂度为 O(1)。

算法核心思想：该算法的核心思路是动态规划。它遍历数组，对于每个位置，计算以该位置元素结尾的连续子数组的最大和。这个最大值要么是当前元素本身，要么是当前元素加上以前一个位置结尾的最大和。同时，用一个变量来记录遍历过程中出现的全局最大和。

具体步骤：

1. 初始化两个变量：

   • current_max 用于记录以当前元素结尾的连续子数组的最大和，初始值设为数组的第一个元素。

   • global_max 用于记录全局最大和，初始值也设为数组的第一个元素。

2. 从数组的第二个元素开始遍历（如果数组不止一个元素）：

   • 对于每个当前元素 nums[i]，更新 current_max： current_max = max(nums[i], current_max + nums[i])这表示以当前元素结尾的最大和，要么是当前元素自己（即放弃之前累加的和），要么是当前元素加上之前的最大和（即继续累加）。

   • 同时，更新 global_max： global_max = max(global_max, current_max)这确保了 global_max 始终是遍历到当前位置为止所遇到的最大子数组和。

3. 遍历结束后，global_max 即为整个数组中连续子数组的最大和。

举例说明：假设数组为 [-2, 1, -3, 4, -1, 2, 1, -5, 4]。

• 初始化：current_max = -2, global_max = -2。

• i=1 (元素1): current_max = max(1, -2+1= -1) = 1; global_max = max(-2, 1)=1。

• i=2 (元素-3): current_max = max(-3, 1-3= -2) = -2; global_max = max(1, -2)=1。

• i=3 (元素4): current_max = max(4, -2+4=2) = 4; global_max = max(1,4)=4。

• i=4 (元素-1): current_max = max(-1, 4-1=3) = 3; global_max = max(4,3)=4。

• i=5 (元素2): current_max = max(2, 3+2=5) = 5; global_max = max(4,5)=5。

• i=6 (元素1): current_max = max(1, 5+1=6) = 6; global_max = max(5,6)=6。

• i=7 (元素-5): current_max = max(-5, 6-5=1) = 1; global_max = max(6,1)=6。

• i=8 (元素4): current_max = max(4, 1+4=5) = 5; global_max = max(6,5)=6。 最终得到最大和为6，对应子数组[4,-1,2,1]。

代码实现（Python示例）：def max_subarray_sum(nums): if not nums: return 0 current_max = global_max = nums[0] for i in range(1, len(nums)): current_max = max(nums[i], current_max + nums[i]) if current_max > global_max: global_max = current_max return global_max

注意特殊情况：如果数组全为负数，该算法也能正确返回最大的那个负数（即绝对值最小的负数）。例如，数组[-3,-1,-2]的最大子数组和是-1。

这种方法高效且易于实现，是解决该问题的标准方案。