【力扣】哈希表經典高頻題

2021-03-02 自然語言處理房室瓣

題目連結

https://leetcode-cn.com/problems/two-sum/description/

題目描述

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

你可以假設每種輸入只會對應一個答案。但是,數組中同一個元素不能使用兩遍。

示例:

給定 nums = [2, 7, 11, 15], target = 9

因為 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

      

思路

遍歷數組 nums,i 為當前下標,n為當前數字,每個值都判斷哈希表中是否存在 target - n 的 key 值。

如果存在則找到了兩個下標值,如果不存在則將當前的 target - n:i 存入 map 中,繼續遍歷直到找到為止。

python代碼

def two_sum(nums, target):    helper = {}    for i, n in enumerate(nums):        if n in helper:            return [helper[n],i]        else:            helper[target - n] = i


相關焦點

  • 哈希函數和哈希表
    其核心就是哈希函數和哈希表的應用!哈希函數哈希函數又稱為散列函數,就是把任意長度的輸入(又叫做預映射, pre-image),通過散列算法,變換成固定長度的輸出,該輸出就是散列值。這種轉換是一種壓縮映射,也就是,散列值的空間通常遠小於輸入的空間,不同的輸入可能會散列成相同的輸出,而不可能從散列值來唯一的確定輸入值。
  • 刷完這70道力扣,你就可以走出新手村啦(文字版)
    之前根據刷題經驗,給大家羅列了70道力扣新手題。後來,我在B站錄製了《手把手帶你刷力扣》的視頻後,又發現了更加適合大家走出新手村的力扣題。這些題目包括了《手把手帶你刷力扣》視頻的全部題目,並且添加了一些對應數據結構和算法的經典題目。
  • 哈希表(散列表)詳解(包含哈希表處理衝突的方法)
    哈希表的建立同函數類似,把函數中的 x 用查找記錄時使用的關鍵字來代替,然後將關鍵字的值帶入一個精心設計的公式中,就可以求出一個值,用這個值來表示記錄存儲的哈希地址。即:數據的哈希地址=f(關鍵字的值)哈希地址只是表示在查找表中的存儲位置,而不是實際的物理存儲位置。
  • 詳解哈希表的查找
    這個映射函數稱為哈希函數,根據這個原則建立的表稱為哈希表(Hash Table),也叫散列表。以上描述,如果通過數學形式來描述就是:若查找關鍵字為 key,則其值存放在 f(key) 的存儲位置上。由此,不需比較便可直接取得所查記錄。註:哈希查找與線性表查找和樹表查找最大的區別在於,不用數值比較。
  • 深入理解哈希表
    哈希表概述Objective-C 中的字典 NSDictionary 底層其實是一個哈希表,實際上絕大多數語言中字典都通過哈希表實現,比如我曾經分析過的 Swift 字典的實現原理。在討論哈希表之前,先規範幾個接下來會用到的概念。哈希表的本質是一個數組,數組中每一個元素稱為一個箱子(bin),箱子中存放的是鍵值對。
  • 哈希表的使用指南
    這個映射函數稱為哈希函數,根據這個原則建立的表稱為哈希表(Hash Table),也叫散列表。以上描述,如果通過數學形式來描述就是:若查找關鍵字為 key,則其值存放在 f(key) 的存儲位置上。由此,不需比較便可直接取得所查記錄。註:哈希查找與線性表查找和樹表查找最大的區別在於,不用數值比較。
  • 數據結構 | 哈希表
    本文為數據結構系列第 11 篇,介紹哈希表的實現。哈希表(也叫散列表)是數據結構課程中都會介紹的概念,一般出現在「散列與查找」相關章節。哈希表的核心思想是構造一個散列函數,鍵值作為散列函數輸入,將元素映射到哈希表某一位置存儲。這樣,在進行查找時就可以根據散列函數快速找到元素所在位置。常見散列函數有:直接定址法、平方取中法、除留餘數法、數字分析法等。
  • PHP哈希表碰撞攻擊原理
    哈希表碰撞攻擊的基本原理哈希表是一種查找效率極高的數據結構,很多語言都在內部實現了哈希表。PHP中的哈希表是一種極為重要的數據結構,不但用於表示Array數據類型,還在Zend虛擬機內部用於存儲上下文環境信息(執行上下文的變量及函數均使用哈希表結構存儲)。
  • Python | Leetcode哈希表系列
    前面文章,點擊下面連結我的Python教程,不斷整理,反覆學習今日,我決定繼續更新Python教程,今天就開始了七十五、Python | Leetcode哈希表系列。哈希表哈希表(散列表)的思想是將關鍵字 Key 映射到存放記錄的散列表中從而進行快速訪問,其中映射函數 f(key) 稱為哈希函數(散列函數),依據哈希函數建立的查找表稱為哈希表。
  • 哈希表:map等候多時了
    set是一個集合,裡面放的元素只能是一個key,而兩數之和這道題目,不僅要判斷y是否存在而且還要記錄y的下表位置,因為要返回x 和 y的下表。所以set 也不能用。此時就要選擇另一種數據結構:map ,map是一種key value的存儲結構,可以用key保存數值,用value在保存數值所在的下表。
  • 理解 Golang 哈希表 Map 的原理
    在上一節中我們介紹了 數組和切片的實現原理,這一節會介紹 Golang 中的另一個集合元素 — 哈希,也就是 Map 的實現原理;哈希表是除了數組之外,最常見的數據結構,幾乎所有的語言都會有數組和哈希表這兩種集合元素,有的語言將數組實現成列表,有的語言將哈希表稱作結構體或者字典,但是它們其實就是兩種設計集合元素的思路,數組用於表示一個元素的序列,而哈希表示的是鍵值對之間映射關係,只是不同語言的叫法和實現稍微有些不同
  • leetcode算法之哈希表
    哈希表哈希表是一種很有用的數據結構, 其作用主要是以空間換時間, 在c++中主要是unordered_set與unordered_map,在python中主要是set與dict.但是,數組中同一個元素不能使用兩遍如果target - nums[i]不在哈希表中就將nums[i]存在哈希表中.遍歷整個數組,對於nums[i], 如果target-nums[i]存在於哈希表中,那就說明找到了這兩個數.使用哈希表(unordered_map)存儲訪問過的元素,這道題需要返回索引,因此鍵為元素的值,值為其對應的索引.
  • 數據結構-PHP 哈希表(Hash Table)的實現
    這篇文章主要介紹一下哈希表(Hash Table)的實現原理,哈希表(Hash Table) 也叫
  • 一看就懂的數據結構基礎「哈希表」
    哈希表哈希表(Hash table),是存儲鍵值(Key Value)對數據的一種數據結構。例如,我們可以將人的名字作為鍵,性別作為值來存儲。通過把鍵映射到表中的一個位置來訪問數據,以提高查找速度。而這個映射關係就是哈希函數。哈希函數因為哈希表的數據映射關係以哈希函數為體現,為了避免小夥伴對哈希函數不夠了解,此處先介紹哈希函數。
  • 為什麼資料庫使用有序索引,而程式設計師卻在使用哈希表?
    常見的答案是,當在內存中存儲數據時,哈希表的效率很高,而B樹的設計旨在以塊的形式訪問較慢的存儲。然而,這不是決定性的屬性。我們也有為訪問磁碟而設計的哈希表,例如MySQL的哈希索引;也有許多在內存中使用的樹,例如Java的TreeMap、C++的映射;甚至連B樹都有內存中使用的版本。
  • 簡單易懂的哈希表總結
    2.1 直接定址法如果我們對盈利為 0-9 的菜品設計哈希表,我們則直接可以根據作為地址,則 f(key) = key;即下面這種情況:有沒有感覺上面的圖很熟悉,沒錯我們經常用的數組其實就是一張哈希表,關鍵碼就是數組的索引下標,然後我們通過下標直接訪問數組中的元素。
  • 7000字哈希表總結,圖文講解!
    今天我們來說一種新的數據結構散列(哈希)表,散列是應用非常廣泛的數據結構,在我們的刷題過程中,散列表的出場率特別高。所以我們快來一起把散列表的內些事給整明白吧,文章框架如下。說散列表之前,我們先設想以下場景。
  • 圖文詳解:7000 字哈希表總結
    今天我們來說一種新的數據結構散列(哈希)表,散列是應用非常廣泛的數據結構,在我們的刷題過程中,散列表的出場率特別高。所以我們快來一起把散列表的內些事給整明白吧,文章框架如下。說散列表之前,我們先設想以下場景。
  • 哈希表的原理,真的很難弄懂麼?
    【Java】基礎25:List、Set以及哈希表昨天學習了幾種簡單數據結構,為何要了解數據結構?一方面的原因是因為集合的底層就是與其息息相關的。HashSet的底層數據結構:哈希表。前天學習了Collection集合,其繼承體系圖如下:今天就來了解Collection的子接口List,Set,以及它們各自的實現類。
  • 圖解:什麼是哈希?
    哈希是對直接訪問表的改進。使用哈希函數將給定的電話號碼或任何其他鍵轉換為較小的數字,將該較小的數字稱為哈希表的索引(哈希值)什麼是哈希表?哈希表和直接訪問表很類似,同樣是一個用於存儲指向給定電話號碼對應記錄的指針的數組,只不過,此時的數組下標不再是電話號碼,而是經過哈希函數映射後的輸出值。什麼是哈希函數?