AI 提示词：力扣算法解题助手

- 题目分析
  - 给定一个整数数组 nums 和目标值 target，要求找到两个不同的下标 i、j，使得 nums[i] + nums[j] == target，返回任意一组解的下标即可（0 基）。
  - 输入格式：
    - 第一行：整数 n（数组长度）
    - 第二行：n 个整数 nums[i]
    - 第三行：整数 target
  - 输出格式：一行输出两个整数 i j（空格分隔）
  - 约束：
    - 2 <= n <= 1e5
    - -1e9 <= nums[i], target <= 1e9
    - 保证至少存在一组解
  - 重点与边界：
    - 需要返回原始下标，不是排序后的位置
    - 可能存在重复元素
    - 可能存在负数
    - 至少一组解保证存在，算法可以在找到第一组解后立即返回

- 解题思路
  - 思路一：暴力枚举（双层循环）
    - 对每个 i，检查所有 j > i，若 nums[i] + nums[j] == target 则返回。
    - 时间复杂度 O(n^2)，空间复杂度 O(1)。
    - 在 n 可达 1e5 时不可行。
  - 思路二：哈希表一次遍历（最优推荐）
    - 使用字典记录已经遍历过的数值及其索引：map[value] = index。
    - 遍历数组当前值 x，计算补数 c = target - x。
    - 若 c 在字典中，则返回 (map[c], 当前索引)；否则将 x 放入字典。
    - 保证不使用同一元素两次，因为只将“之前出现的元素”存入字典。
    - 时间复杂度 O(n)，空间复杂度 O(n)。
  - 思路三：排序 + 双指针
    - 将数组元素与索引一起存储为 (value, index) 对，按 value 排序。
    - 用双指针从两端逼近求和，找到满足条件的两个索引。
    - 时间复杂度 O(n log n)，空间复杂度 O(n)（存储对）。
    - 缺点：需要额外处理返回原始下标；相较哈希法更慢。

- 算法设计（选定方案：哈希表一次遍历）
  - 初始化一个空字典 seen，用于记录已遍历过的数字及其下标。
  - 遍历 i 从 0 到 n-1：
    - 令 x = nums[i]，计算补数 c = target - x。
    - 若 c 在 seen 中，返回 seen[c] 和 i。
    - 否则，将 seen[x] = i 存入字典。
  - 因为题目保证有解，遍历过程中必然能返回一组下标。
  - 边界与正确性：
    - 当 target = 2*x 且数组中有两个相等的值 x 时：第一次遇到 x 将其存入字典，第二次遇到相同 x 时其补数仍是 x，字典命中返回两个不同的索引。
    - 处理负数和大数对 Python 没有问题，整数无溢出。

- 代码实现（Python）
```python
import sys

def two_sum(nums, target):
    """
    返回任意一对满足 nums[i] + nums[j] == target 的不同下标 (i, j)。
    使用哈希表实现 O(n) 时间复杂度。
    """
    seen = {}  # value -> index
    for i, x in enumerate(nums):
        c = target - x
        if c in seen:
            return seen[c], i
        # 只在未命中时记录当前值及索引，确保不使用同一元素两次
        seen[x] = i
    # 按题意保证至少有解，这里理论上不会到达
    return -1, -1

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    # 解析输入
    it = iter(data)
    n = int(next(it))
    nums = [int(next(it)) for _ in range(n)]
    target = int(next(it))

    i, j = two_sum(nums, target)
    print(f"{i} {j}")

if __name__ == "__main__":
    main()
```

- 复杂度分析
  - 时间复杂度：O(n)
    - 每个元素最多一次哈希查找与一次插入，哈希操作均摊 O(1)。
  - 空间复杂度：O(n)
    - 在最坏情况下需要存储所有已遍历元素的值与索引。

- 测试用例
  - 基本用例（示例）
    - 输入：
      4
      2 7 11 15
      9
    - 输出：0 1
  - 重复元素
    - 输入：
      5
      3 3 4 5 6
      6
    - 输出：0 1（或 1 0）
  - 负数与零
    - 输入：
      5
      -1 0 1 2 -2
      -1
    - 输出：0 1（-1 + 0 = -1）或 4 2（-2 + 1 = -1）
  - 大数与跨界组合
    - 输入：
      3
      1000000000 -1000000000 5
      5
    - 输出：0 1（1e9 + (-1e9) = 0，不满足；正确应为 2 与某个数 -> 此例请换 target=5）
    - 更正用例：
      3
      1000000000 -999999995 5
      5
    - 输出：0 1（1e9 + (-999999995) = 5）
  - 相同值满足 target = 2*x
    - 输入：
      4
      5 5 1 9
      10
    - 输出：0 1（两个 5 相加等于 10）

## 题目分析
- 问题本质：判断有向图是否存在环。课程之间的先修关系构成一个有向图，若图不存在有向环，则可完成所有课程；若存在环，则不可完成。
- 输入输出：
  - 输入：
    - 第一行：numCourses（课程总数）
    - 第二行：m（先修关系条数）
    - 接下来 m 行：a b，表示课程 a 需要先修课程 b，即有边 b -> a
  - 输出：一行 "true" 或 "false"
- 约束：
  - 1 <= numCourses <= 1e5
  - 0 <= m <= 2e5
  - 0 <= a, b < numCourses
  - 需要时间复杂度 O(numCourses + m)

## 解题思路
常见两种方法：
1. 拓扑排序（Kahn 算法，BFS）
   - 思想：统计每个节点的入度，将入度为 0 的课程入队，逐步“上课”并移除其对后继课程的影响（后继入度减 1）。最终若能处理完所有课程（出队计数等于 numCourses），则无环；否则有环。
   - 优点：迭代实现，无递归栈风险；时间 O(n + m)，空间 O(n + m)。
   - 适合本题大规模数据。

2. DFS 检测环
   - 思想：对每个未访问节点进行 DFS，使用三色标记（0=未访问, 1=访问中, 2=已完成）。在访问中再次遇到访问中的节点，说明存在回边（有向环）。
   - 优点：实现简洁，直观。
   - 缺点：Java 在最坏情况下（长链）可能栈溢出；需注意递归深度限制。

对比与选择：
- 在本题规模下（最多 1e5 节点、2e5 边），推荐使用 Kahn 拓扑排序（BFS），更稳健，不会栈溢出。DFS 方法可作为参考实现。

## 算法设计（选定：Kahn 拓扑排序）
- 数据结构：
  - 邻接表 graph：ArrayList<Integer>[]，graph[u] 存储从 u 指向的后继 v（b -> a）
  - 入度数组 indeg：indeg[v] 表示 v 的入度
  - 队列 queue：存入所有入度为 0 的节点
- 步骤：
  1. 初始化邻接表和入度数组。
  2. 遍历所有先修关系 (b -> a)，填充 graph[b].add(a)，并 indeg[a]++。
  3. 将所有入度为 0 的课程入队。
  4. 出队一个课程 u，计数 processed++；遍历 u 的后继 v，执行 indeg[v]--；若 indeg[v] == 0，则入队 v。
  5. 循环结束后，若 processed == numCourses，则返回 true；否则返回 false。
- 边界情况处理：
  - m == 0：所有课程入度均为 0，直接返回 true。
  - 自环（a == b）：会导致 indeg[a] >= 1，最终 processed < numCourses，返回 false。
  - 重边（重复的先修关系）：入度会相应累加，拓扑排序正确处理。

## 代码实现（Java）
说明：
- 提供两种方法：Kahn（主方法）与 DFS（参考）。
- 包含 main 方法，按题目输入格式读取并输出结果。
- 同时提供 LeetCode 风格的 canFinish 方法。

```java
import java.io.*;
import java.util.*;

/**
 * 课程表（是否可修完）
 * 方法一：Kahn 拓扑排序（BFS） —— 推荐
 * 方法二：DFS 检测有向环 —— 参考（可能有递归栈风险）
 */
public class Solution {

    // LeetCode风格函数
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        return canFinishKahn(numCourses, prerequisites);
    }

    // 方法一：Kahn 拓扑排序
    public boolean canFinishKahn(int n, int[][] prerequisites) {
        // 邻接表
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
        // 入度
        int[] indeg = new int[n];

        // 构图：b -> a
        for (int[] e : prerequisites) {
            int a = e[0], b = e[1];
            graph[b].add(a);
            indeg[a]++;
        }

        // 入度为0的节点入队
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) queue.offer(i);
        }

        int processed = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            processed++;
            for (int v : graph[u]) {
                if (--indeg[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        return processed == n;
    }

    // 方法二：DFS 检测环（参考实现）
    public boolean canFinishDFS(int n, int[][] prerequisites) {
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
        for (int[] e : prerequisites) {
            int a = e[0], b = e[1];
            graph[b].add(a);
        }
        // 0=未访问, 1=访问中, 2=已完成
        int[] state = new int[n];

        for (int i = 0; i < n; i++) {
            if (state[i] == 0) {
                if (dfsHasCycle(i, graph, state)) {
                    return false; // 有环则不可完成
                }
            }
        }
        return true;
    }

    private boolean dfsHasCycle(int u, List<Integer>[] graph, int[] state) {
        state[u] = 1; // 标记为访问中
        for (int v : graph[u]) {
            if (state[v] == 1) return true;         // 回边：有环
            if (state[v] == 0 && dfsHasCycle(v, graph, state)) return true;
        }
        state[u] = 2; // 完成
        return false;
    }

    // 主程序：按题目输入格式读取并输出
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;

        s = br.readLine();
        if (s == null) return;
        int numCourses = Integer.parseInt(s.trim());

        s = br.readLine();
        int m = Integer.parseInt(s.trim());

        int[][] prerequisites = new int[m][2];
        for (int i = 0; i < m; i++) {
            String line = br.readLine();
            StringTokenizer st = new StringTokenizer(line);
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            prerequisites[i][0] = a;
            prerequisites[i][1] = b;
        }

        Solution sol = new Solution();
        boolean ans = sol.canFinishKahn(numCourses, prerequisites);
        System.out.println(ans ? "true" : "false");
    }
}
```

## 复杂度分析
- 时间复杂度：
  - 构图 O(n + m)
  - Kahn 拓扑排序遍历每条边一次 O(m)，每个节点入队、出队一次 O(n)
  - 总计 O(n + m)
- 空间复杂度：
  - 邻接表存储 O(n + m)
  - 入度数组 O(n)
  - 队列最多 O(n)
  - 总计 O(n + m)

## 测试用例
- 示例1：
  - 输入：
    - numCourses=2, m=1
    - 1 0
  - 输出：true
- 示例2：
  - 输入：
    - numCourses=2, m=2
    - 1 0
    - 0 1
  - 输出：false
- 边界用例：
  - 无先修关系：
    - 输入：numCourses=5, m=0
    - 输出：true
  - 自环：
    - 输入：numCourses=1, m=1
    - 0 0
    - 输出：false
  - 长链（压力测试，栈安全性验证对 DFS 不利）：
    - 输入：numCourses=5, m=4
    - 1 0
    - 2 1
    - 3 2
    - 4 3
    - 输出：true

说明：在大规模数据下建议采用 Kahn 拓扑排序方案，避免递归带来的栈溢出风险。

## 题目分析
- 目标：实现一个支持 get 和 put 操作的 LRU（最近最少使用）缓存。
- 约束：
  - 容量 cap 与操作数 q 均可达 1e5，需要均摊 O(1) 的操作。
  - 键值可能为负数，范围 [-1e9, 1e9]。
- 输入输出：
  - 输入 cap 与 q，然后 q 行操作：get k 或 put k v。
  - 输出所有 get 的返回值，每行一个。
- 核心要求：使用哈希表 + 双向链表 组合，保证均摊 O(1)。

## 解题思路
- 暴力（不合格）：用数组或链表存键值，每次 get/put 线性查找并维护使用顺序，复杂度 O(n)，在 q=1e5 时无法满足性能要求。
- 标准解（推荐）：使用
  - 哈希表（unordered_map）：key -> 双向链表节点迭代器，O(1) 查找
  - 双向链表（std::list）：维护使用顺序，表头为最近使用，表尾为最久未使用
- 操作逻辑：
  - get(k)：若存在，将节点移至表头并返回值；否则返回 -1
  - put(k, v)：
    - 若 k 已存在：更新值并移至表头
    - 若 k 不存在：
      - 容量未满：在表头插入新节点
      - 容量已满：删除表尾节点（LRU），再在表头插入新节点
- 数据结构选择：
  - 使用 std::list<pair<long long, long long>> 存 (key, value)
  - 使用 unordered_map<long long, list<...>::iterator> 存位置
  - 使用 list::splice 在 O(1) 时间内移动节点到表头

## 算法设计
- 维护：
  - list L，头部 L.begin() 为最近使用，尾部 L.back() 为最久未使用
  - unordered_map pos：key -> L 中对应节点迭代器
- get(key)：
  1. 在 pos 中查找；不存在返回 -1
  2. 使用 splice 将该节点移到表头
  3. 返回节点的 value
- put(key, value)：
  1. cap 为 0 时直接返回（防御性处理）
  2. 在 pos 中查找：
     - 若存在：更新节点 value，splice 到表头
     - 若不存在：
       - 若 L.size() == cap：取尾节点，先在 pos 中删除其 key，再 pop_back
       - 在表头 emplace_front 新节点，并在 pos 中记录其迭代器
- 边界与细节：
  - 负数 key/value 正常支持
  - 多次 put 同一 key，应更新并提升为最近使用
  - 仅 get 输出结果
  - 使用 fast I/O，unordered_map 预留容量以减少 rehash

## 代码实现（C++）
```cpp
#include <bits/stdc++.h>
using namespace std;

class LRUCache {
public:
    using K = long long;
    using V = long long;
    using Node = pair<K, V>;

    LRUCache(size_t capacity) : cap(capacity) {
        // 预留哈希表空间，减少 rehash 次数
        pos.reserve(capacity ? capacity : 1);
    }

    int get(K key) {
        auto it = pos.find(key);
        if (it == pos.end()) return -1;
        // 将此节点移动到链表头部（最近使用）
        cache.splice(cache.begin(), cache, it->second);
        return static_cast<int>(it->second->second);
    }

    void put(K key, V value) {
        if (cap == 0) return; // 防御：容量为 0，则不存储任何键

        auto it = pos.find(key);
        if (it != pos.end()) {
            // 更新值并移动到头部
            it->second->second = value;
            cache.splice(cache.begin(), cache, it->second);
            return;
        }

        // 若容量已满，移除尾部（最久未使用）
        if (cache.size() == cap) {
            auto lastIt = prev(cache.end());
            K kEvict = lastIt->first;
            pos.erase(kEvict);
            cache.pop_back();
        }

        // 在头部插入新节点
        cache.emplace_front(key, value);
        pos[key] = cache.begin();
    }

private:
    size_t cap;
    list<Node> cache;                              // 双向链表：头=最近，尾=最久
    unordered_map<K, list<Node>::iterator> pos;    // 哈希：key -> 节点迭代器
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long cap;
    int q;
    if (!(cin >> cap)) return 0;
    cin >> q;

    LRUCache lru(static_cast<size_t>(cap));

    for (int i = 0; i < q; ++i) {
        string op;
        cin >> op;
        if (op == "get") {
            long long k;
            cin >> k;
            cout << lru.get(k) << "\n";
        } else if (op == "put") {
            long long k, v;
            cin >> k >> v;
            lru.put(k, v);
        } else {
            // 非法操作名：忽略或可选择处理，这里忽略
        }
    }
    return 0;
}
```

## 复杂度分析
- 时间复杂度：
  - get 与 put 均为均摊 O(1)
    - 哈希查找 O(1) 平均
    - list 的 splice、插入、删除均为 O(1)
- 空间复杂度：
  - O(cap) 存储双向链表与哈希表

## 测试用例
- 示例用例：
  - 输入：
    2
    9
    put 1 1
    put 2 2
    get 1
    put 3 3
    get 2
    put 4 4
    get 1
    get 3
    get 4
  - 输出：
    1
    -1
    -1
    3
    4
- 边界与功能覆盖：
  1. 容量为 1，频繁替换
     - 输入：
       1
       5
       put 1 10
       put 2 20
       get 1
       put 2 30
       get 2
     - 期望输出：
       -1
       30
  2. 重复 put 同一键提升最近性
     - 输入：
       2
       6
       put 1 1
       put 2 2
       put 1 10
       put 3 3
       get 2
       get 1
     - 期望输出：
       -1
       10
  3. 不存在的键
     - 输入：
       2
       3
       put 1 1
       get 2
       get 1
     - 期望输出：
       -1
       1
  4. 负数键与值
     - 输入：
       2
       5
       put -1 -100
       put -2 -200
       get -1
       put -3 -300
       get -2
     - 期望输出：
       -100
       -1
  5. 全是 put（无输出）
     - 输入：
       2
       3
       put 1 1
       put 2 2
       put 3 3
     - 期望输出：空输出（无行）
  6. 防御性测试：cap=0（若平台允许）
     - 输入：
       0
       4
       put 1 1
       get 1
       put 2 2
       get 2
     - 期望输出：
       -1
       -1

该实现符合题目对 LRU 的期望：哈希表 + 双向链表，操作均摊 O(1)，并覆盖常见边界情况。