1. 兩數之和

1

題目

給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 target 的那兩個整數，並返回它們的數組下標。

你可以假設每種輸入只會對應一個答案，並且你不能使用兩次相同的元素。

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

示例 1：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1]

提示：

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只會存在一個有效答案

2

代碼

rust

use std::collections::HashMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut map: HashMap<i32, usize> = HashMap::with_capacity(nums.len());
        for (i, &n) in nums.iter().enumerate() {
            if let Some(&j) = map.get(&(target - n)) {
                return vec![j as i32, i as i32];
            }
            map.insert(n, i);
        }
        vec![]
    }
}

3

思路

一次遍歷，哈希表記錄 值 → 索引。對每個 n，查 target - n 是否在表中：

在：直接返回
不在：把 n 寫入表

時間 O(n)，空間 O(n)，是這一題的最優解。

graph TD
    A[開始] --> B[遍歷 nums]
    B --> C{target - n 在 map 中?}
    C -->|是| D[返回索引對]
    C -->|否| E[把 n 寫入 map]
    E --> F{遍歷完?}
    F -->|否| B
    F -->|是| G[返回空]
    D --> H[結束]
    G --> H