問題描述

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

你可以假設(shè)每種輸入只會(huì)對應(yīng)一個(gè)答案。但是，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素。

Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Solution：

public static int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();// 建立值與下標(biāo)對應(yīng)關(guān)系for(int i = 0; i<nums.length; i++){map.put(nums[i], i);}// 獲取鍵集合int[] arr = new int[2];for(int i = 0; i < nums.length; i++){int complement = target - nums[i];if(map.containsKey(complement) && map.get(complement) != i){arr[0] = i;arr[1] = map.get(complement);}}return arr;}

對于輸入為[ 3, 3 ]，target = 6 的測試case，我們要如何理解？

首先，在Map 中，相同的key 如果存在，那么舊的key 對應(yīng)的 值就會(huì)被覆蓋掉，第一個(gè) for 循環(huán)結(jié)束后，map 中只有一個(gè)鍵值對，即：{ 3 = 1 }，這并不會(huì)影響結(jié)果，只不過在 arr[0] 賦值的時(shí)候，需要注意，一定不要使用 arr[0] = map.get(nums[i]); 這種寫法，看似與上面的正確解法語義上相同，但是卻忽視了相同元素被覆蓋掉的情況。

總結(jié)

上段代碼引用了LeetCode上此問題支持率最高的解決方法。

看到題目的時(shí)候我是正常的用了二重for循環(huán)進(jìn)行求解的，在LeetCode中也有我那種解法，他們稱之為：Brute Force。

而上面貼出來的這種解法思路在于考慮到了時(shí)間復(fù)雜度。這里又不得不記錄一下我收集到了對時(shí)間復(fù)雜度的理解：

基本操作執(zhí)行次數(shù)與問題規(guī)模n成正比。

時(shí)間復(fù)雜度 共有八個(gè)同數(shù)量級分別是：1，log2n，n，n log2n，n^2，n^3，2^n，n! ?

從 1 到 n! 時(shí)間復(fù)雜度依次增高。二重for循環(huán)記作O(n^2)，三重for循環(huán)記作O(n^3)依此類推。

解釋是這樣的：To improve our run time complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to look up its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.

為了改進(jìn)我們運(yùn)行時(shí)間的復(fù)雜程度，我們需要更有效的方法去array中檢查是否有一個(gè)特定的“補(bǔ)足數(shù)”存在，如果存在，我們就去找他的index。那么維護(hù)數(shù)組元素與其下標(biāo)之間的映射關(guān)系最好的途徑是什么呢？沒錯(cuò)，就是 hash 表。

這句話給我的印象特別深。那么如果下一次又出現(xiàn)一個(gè)問題要求我們找到兩組值的對應(yīng)關(guān)系的話，我們首先就會(huì)考慮到哈希表。這正是我希望得到的東西，一種思考的方向。

We reduce the look up time from O(n) to O(1) by trading space for speed. A hash table is built exactly for this purpose, it supports fast look up in near constant time. I say "near" because if a collision occurred, a look up could degenerate to O(n) time. But look up in hash table should be amortized O(1) time as long as the hash function was chosen carefully.

我們通過犧牲空間換取速度的方式來將時(shí)間復(fù)雜度從O(n)到O(1)。哈希表的建立正是為此目的，它支持在近乎不變的時(shí)間內(nèi)快速查找。

?

?

總結(jié)

以上是生活随笔為你收集整理的LeetCode(#1)————Two Sum的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。