🍀題目

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

你可以假設每種輸入只會對應一個答案。但是，數(shù)組中同一個元素在答案里不能重復出現(xiàn)。

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

---

🍀解法一

暴力解法，最先想到的方法
但是在運行的時候出現(xiàn)了一個問題

 for i in len(nums):for j in range(i+1, len(nums)):if nums[i]+nums[j]==target:return [i,j]

但是報錯了（還是本人基本語法掌握不好）

經(jīng)查閱后

錯誤消息"TypeError: ‘int’ object is not iterable"通常在Python中出現(xiàn)，當您嘗試像遍歷（循環(huán)）可迭代對象一樣遍歷整數(shù)（int）值時，比如列表、元組或字符串等時會出現(xiàn)此錯誤。在Python中，您只能遍歷支持迭代的對象，如序列和集合。總的來看：列表、字典、集合、元組、字符串可迭代；整數(shù)、浮點數(shù)、布爾、NoneType不可迭代

修改后的代碼如下

n = len(nums)for i in range(n):for j in range(i+1, n):if nums[i]+nums[j]==target:return [i,j]

補充：range(n) 創(chuàng)建的對象是一個類似于序列的可迭代對象，但它實際上并不存儲整個范圍內(nèi)的所有值，而是根據(jù)需要生成這些值，從而節(jié)省內(nèi)存空間。這種懶加載（lazy loading）的方式使得 range 在處理大范圍的整數(shù)時非常高效

---

🍀解法二

思路及算法

注意到方法一的時間復雜度較高的原因是尋找 target - x 的時間復雜度過高。因此，我們需要一種更優(yōu)秀的方法，能夠快速尋找數(shù)組中是否存在目標元素。如果存在，我們需要找出它的索引。

使用哈希表，可以將尋找 target - x 的時間復雜度降低到從 O(N)O(N)O(N) 降低到 O(1)O(1)O(1)。

這樣我們創(chuàng)建一個哈希表，對于每一個 x，我們首先查詢哈希表中是否存在 target - x，然后將 x 插入到哈希表中，即可保證不會讓 x 和自己匹配。

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:hashtable = dict()for i, num in enumerate(nums):if target - num in hashtable:return [hashtable[target - num], i]hashtable[nums[i]] = ireturn []

官方給出的答案里，有些函數(shù)和語句可能不太了解，這里我說明一下

• dict()是創(chuàng)建一個空字典

• enumerate() 是一個內(nèi)置函數(shù)，用于在迭代過程中同時獲取索引和元素值，通常用于循環(huán)遍歷列表、元組、字符串等可迭代對象時。其基本語法如下：

• hashtable[nums[i]] = i 的作用是將列表中的元素作為鍵，將其索引作為值，存儲到一個哈希表（字典）中。這個哈希表可以用來快速查找特定元素在列表中的索引，因為字典的鍵是唯一的，通過元素值可以直接定位到其索引。

  iterable 是要枚舉的可迭代對象，如列表、元組、字符串等。
  start 是可選參數(shù)，表示索引起始值，默認為0，但你可以指定一個不同的起始值。
  enumerate() 返回一個迭代器，每次迭代都產(chǎn)生一個元組，包含兩個值：索引和元素值。索引從指定的起始值開始遞增。

---

🍀哈希表

哈希表（Hash Table），也被稱為散列表，是一種常見的數(shù)據(jù)結構，用于高效地存儲和檢索鍵值對（key-value pairs）。哈希表的核心思想是通過將鍵（key）映射到一個確定的位置（索引）來實現(xiàn)快速的數(shù)據(jù)訪問。這個映射函數(shù)被稱為哈希函數(shù)（hash function）。

以下是哈希表的主要特點和工作原理：

• 快速查找： 哈希表的主要優(yōu)勢在于它可以在平均情況下（取決于哈希函數(shù)的質(zhì)量和哈希表的實現(xiàn)方式）提供常數(shù)時間復雜度的查找操作，即O(1)時間復雜度。

• 哈希函數(shù)： 哈希表的關鍵部分是哈希函數(shù)，它將鍵映射到哈希表中的一個位置。好的哈希函數(shù)應該盡可能均勻地分布鍵，以減少沖突（多個鍵映射到同一位置）的發(fā)生。沖突是哈希表需要解決的主要問題之一。

• 沖突解決： 當兩個不同的鍵經(jīng)過哈希函數(shù)映射到同一位置時，就發(fā)生了沖突。哈希表有多種方法來解決沖突，包括鏈地址法（Chaining）、開放尋址法（Open Addressing）等。每種方法都有自己的優(yōu)點和適用場景。

• 動態(tài)擴展： 哈希表通常會動態(tài)擴展，以處理更多的鍵值對。當表格裝填因鍵值對的添加而變得過高時，哈希表會重新調(diào)整大小，以保持其性能。

• 無序性： 哈希表是無序的數(shù)據(jù)結構，鍵值對的順序不一定與它們被添加到哈希表的順序相同。

哈希表在計算機科學中有廣泛的應用，常見用途包括實現(xiàn)字典、集合、緩存等數(shù)據(jù)結構，以及在數(shù)據(jù)庫索引、哈希表查找等領域中的優(yōu)化。哈希表的性能取決于哈希函數(shù)的質(zhì)量和解決沖突的方法，因此在設計和使用哈希表時，需要注意選擇合適的哈希函數(shù)和解決沖突的策略，以確保其高效性和穩(wěn)定性。

---

挑戰(zhàn)與創(chuàng)造都是很痛苦的，但是很充實。