法蘭克無極限
Published in

法蘭克無極限

LeetCode: 1.Two Sum (Java)

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

給予一個 nums 的整數陣列和一個整數 target 變數,回傳其中二個數字的陣列索引值,足二個數字的加總等於 target。

你可以假設就只有一個正確的解,而且也不能使用相同的數字二次。

傳回的答案可以是任何順序。

Solution 1: 暴力二層迴圈

Runtime: 0 ms, faster than 100.00%

Memory Usage: 38.9 MB, less than 92.80%

Solution 2: HashMap方式

Runtime: 0 ms, faster than 100.00%

Memory Usage: 39 MB, less than 79.44%

此方式使用Java已優化之HashMap類別,其containsKey、put與get之時間複雜度為O(1),所以時間複雜度為O(n)。

若初學者覺得困難,也可以先用另一個迴圈,把nums的鍵(key)與值(value)放入HashMap中,雖然多一個迴圈較慢一些,但所得到的時間複雜度一樣是O(n)。而上面解法則是運用到倒序比對的想法,便能少一個迴圈,這種技巧在迴圈程式寫作中,很常利用到。

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store