題目

給定一個整數(shù)數(shù)組 nums 和一個整數(shù)目標值 target，請你在該數(shù)組中找出 和為目標值 target 的那 兩個 整數(shù)，并返回它們的數(shù)組下標。
你可以假設每種輸入只會對應一個答案。但是，數(shù)組中同一個元素在答案里不能重復出現(xiàn)。

Two Sum 問題分步教程

步驟 1：理解問題

首先，我們需要理解題目的要求。對于 Two Sum 問題，題目要求在給定的整數(shù)數(shù)組中找到兩個整數(shù)，使它們的和等于目標值。我們需要返回這兩個整數(shù)的數(shù)組下標。

步驟 2：分析問題

在分析問題時，我們可以考慮不同的解決方案。對于 Two Sum 問題，一種簡單直觀的方法是使用兩層循環(huán)遍歷所有可能的組合，找到和等于目標值的那一對。然而，這樣的解法時間復雜度較高（O(n^2)），不是最優(yōu)解。更高效的方法是使用哈希表。

步驟 3：選擇數(shù)據(jù)結構

為了提高解決問題的效率，我們選擇使用哈希表來存儲已經遍歷過的數(shù)字及其對應的下標。這樣可以在 O(1) 的時間內查找數(shù)字是否存在于數(shù)組中。

步驟 4：算法設計

1. 創(chuàng)建一個空的哈希表（Map 或對象）numberIndexMap，用于存儲已經遍歷過的數(shù)字及其對應的下標。
2. 遍歷數(shù)組 nums。
3. 對于每個數(shù)字 nums[i]，計算其補數(shù) complement，即 target - nums[i]。
4. 檢查補數(shù)是否已經在哈希表中存在。
   如果存在，說明找到了兩個數(shù)的和等于目標值，直接返回它們的下標。
   如果不存在，將當前數(shù)字及其下標存入哈希表中。
   如果遍歷完整個數(shù)組都沒有找到符合條件的兩個數(shù)，返回一個空數(shù)組。

步驟 5：實現(xiàn)算法

根據(jù)上述算法設計，我們可以用 TypeScript 編寫代碼實現(xiàn) Two Sum 問題的解決方案。

/**
 * 在給定的整數(shù)數(shù)組中找到兩個整數(shù)，使它們的和等于目標值。
 * @param {number[]} nums - 整數(shù)數(shù)組
 * @param {number} target - 目標值
 * @returns {number[]} 包含兩個整數(shù)的數(shù)組，它們的和等于目標值的下標
 */
function twoSum(nums: number[], target: number): number[] {
    // 創(chuàng)建一個哈希表，用于存儲已經遍歷過的數(shù)字及其對應的下標
    const numberIndexMap: Record<number, number> = {};
    // 遍歷數(shù)組
    for (let i = 0; i < nums.length; i++) {
        // 計算當前數(shù)字的補數(shù)
        const complement = target - nums[i];
        // 檢查補數(shù)是否已經在哈希表中存在
        if (complement in numberIndexMap) {
            // 如果存在，直接返回包含兩個數(shù)字下標的數(shù)組
            return [numberIndexMap[complement], i];
        }
        // 如果不存在，將當前數(shù)字及其下標存入哈希表中
        numberIndexMap[nums[i]] = i;
    }
    // 如果沒有找到符合條件的兩個數(shù)字，返回一個空數(shù)組
    return [];
}
// 示例
const nums = [3, 2, 4];
const target = 6;
// 調用函數(shù)，獲取結果并輸出
const result = twoSum(nums, target);
console.log(result);

步驟 6：測試和調試

在實現(xiàn)完算法后，我們需要進行測試和調試，確保代碼能夠正確運行?？梢酝ㄟ^給定的示例和其他測試用例進行驗證。

步驟 7：復雜度分析

最后，我們對算法的時間復雜度進行分析。在這個算法中，哈希表的插入和查找操作的平均時間復雜度是 O(1)，因此整體算法的時間復雜度是 O(n)。

通過以上步驟，我們完成了 Two Sum 問題的分析、設計和實現(xiàn)。希望這個教程能夠幫助你更好地理解算法問題的解決過程。