圖解演算法第一彈：兩數之和｜瞭解一下？

文 | 極客日記

兩數之和

題目來源於 LeetCode［1］，第一題。

1。 題目描述

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

你可以假設每種輸入只會對應一個答案。但是，你不能重複利用這個陣列中同樣的元素。

示例：

給定 nums = ［2， 7， 11， 15］， target = 9

因為 nums［0］ + nums［1］ = 2 + 7 = 9

所以返回 ［0， 1］

2。 解題思路

題目的意思是想讓我們從給定的 nums 陣列中，找到兩個相加等於 target 的數 a 和 b 並返回這兩個數在陣列中對應的下標 i 和 j。

具體思路如下：

定義一個對映關係map，map 中儲存的資料結構形如 ，其中 k∈［0， nums。length）；

遍歷給定的陣列

如果 nums［k］ 存在於 map 的 key鍵中，則 key鍵 對應的 value值和當前的 k值 就是我們要找的兩個下標；

如果 nums［k］ 不存在於 map 的 key鍵中，則把 儲存到 map中；

迴圈結束。

3。 演算法動畫

假設給定陣列 nums 為 ［2， 7， 11， 15］，目標值 target 等於9，依照上面給出的演算法，執行過程如下圖：

圖解兩數之和

4。 程式碼實現

個人精力有限，目前只有 Java 程式碼的演算法實現，後續可能會考慮增加其他語言的實現，敬請期待哦~

4.1 Java 實現