每天一題LeetCode[第二天]

ToSum

Description:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

Example:

解題過程：

首先題意十分簡單易懂，給你一個(gè)整數(shù)類型的數(shù)組，在給你一個(gè)整數(shù)target，找出相加等于target的兩個(gè)數(shù)的indices。

第一個(gè)思路就是窮舉查找滿足條件的兩個(gè)數(shù)，時(shí)間復(fù)雜度o(n^2)，這是誰都能想到的思路，最好的結(jié)果肯定不是這樣。優(yōu)化：基于這樣的思路，去除不可能的結(jié)果把數(shù)組中大于target的數(shù)去掉 減少n的值，但是這種復(fù)雜度也是o(n^2) 在細(xì)想，發(fā)現(xiàn)，只要基于這樣的思想是沒辦法繼續(xù)優(yōu)化的。必須發(fā)現(xiàn)target 與兩個(gè)結(jié)果 之間的特殊關(guān)系。

看了top solution 真是佩服！怎么說呢，這樣吧，a+b=c 那么如果說對于nums來說，在遍歷過程中能提前知道每個(gè)數(shù)字相對于c的補(bǔ)數(shù)，并且知道這個(gè)數(shù)的下表，那么這一切就很簡單了。 因?yàn)槭莂+b=c 所以不用擔(dān)心一次循環(huán)會(huì)錯(cuò)過結(jié)果，因?yàn)橐欢〞?huì)經(jīng)過a 和b的。 當(dāng)經(jīng)過a的時(shí)候 就記錄下b的值 和 a的下標(biāo) 這樣在經(jīng)過b的時(shí)候就知道 喔這就是我要的答案。 細(xì)想了一下，就是讓每一步計(jì)算 的結(jié)果都有意義，相比于第一個(gè)結(jié)果很明顯的是，第一種思路 ，每一步的計(jì)算意義都是為了從總的可能數(shù)中減去一，或者可以這樣說，每一步的計(jì)算 之間關(guān)聯(lián)不大，所以每一步的計(jì)算都顯得繁瑣。而第二種的思路，把每一步的計(jì)算的信息保存下來，對下一次的計(jì)算都起到了極大的幫助，大大簡化了計(jì)算量。

top solution對java集合類很熟悉，運(yùn)用了map的數(shù)據(jù)結(jié)構(gòu)特點(diǎn)（索引快，），雖然增加了存儲(chǔ)空間，但是時(shí)間復(fù)雜度在這個(gè)時(shí)代才是關(guān)鍵。

Java代碼：

提高代碼質(zhì)量就是：每天積累精美的思路，優(yōu)質(zhì)的細(xì)節(jié)的過程。