每天一題LeetCode[第二天]

ToSum

Description:

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

Example:

解題過程：

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

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

看了top solution 真是佩服！怎么說呢，這樣吧，a+b=c 那么如果說對于nums來說，在遍歷過程中能提前知道每個數字相對于c的補數，并且知道這個數的下表，那么這一切就很簡單了。 因為是a+b=c 所以不用擔心一次循環會錯過結果，因為一定會經過a 和b的。 當經過a的時候 就記錄下b的值 和 a的下標 這樣在經過b的時候就知道 喔這就是我要的答案。 細想了一下，就是讓每一步計算 的結果都有意義，相比于第一個結果很明顯的是，第一種思路 ，每一步的計算意義都是為了從總的可能數中減去一，或者可以這樣說，每一步的計算 之間關聯不大，所以每一步的計算都顯得繁瑣。而第二種的思路，把每一步的計算的信息保存下來，對下一次的計算都起到了極大的幫助，大大簡化了計算量。

top solution對java集合類很熟悉，運用了map的數據結構特點（索引快，），雖然增加了存儲空間，但是時間復雜度在這個時代才是關鍵。

Java代碼：

提高代碼質量就是：每天積累精美的思路，優質的細節的過程。