獨遊開發新人的刷題筆記01：兩數之和

大家好呀，這裏是獨立遊戲開發新人題語的算法小課堂。

嗯，最近呢在籌備自己的第一款獨立遊戲（但大部分地方都還剛剛起步，等到完成還要好久好久呢），想是提前積累積累寫專欄的經驗嘛。

所以呢，就從我接觸比較多的算法開始啦，希望能幫助到大家啊。

之後，可能也會增加開發相關的專欄（畫個大餅先hhh)，也請各位大佬前輩們多多指教啊。

提前說明一下題目來源均是力扣，有興趣的盒友也可以去看看啊。

主要本人最近也在準備408的考研，所以題解均主要使用C語言，後續也可能會添加其他語言，還望盒友們海涵。

嗯，下面我們就開始吧。今天是一道關於數組操作的簡單題，兩數之和。

題目要求

接下來是我們需要補全的函數。

待補全的函數

開始解題！

首先，我們觀察需要補全函數的輸入與輸出，可以發現輸入從左到右分別爲 輸入的整數數組nums，輸入的整數數組的大小numsSize，整數目標值target，返回數組的大小returnSize；輸出爲返回的目標數組。

第一種方法暴力求解，雙循環。

看完了函數的輸入和返回值後，我們再來看題目對應的解題要求，需要找出和爲目標值的兩個整數。

我們可以很容易想到一種時間複雜度較高的暴力求解方法，就是將輸入的整數數組中每種元素的組合都逐一都列出，直至找到和爲目標值的組合後，返回組合數組。

根據以上思想，我們就可以構建出整體代碼。

首先，申請我們需要返回的數組的空間

申請空間

然後，因爲需要找出整數數組中每種元素的組合，我們可以構建一個雙循環的結構

雙循環結構

爲什麼j需要等於i + 1呢？主要呢是爲了防止組合出現重複以及組合中的元素出現重複。

好了，我們已經成功找到了所有的組合。接下來，我們就應該來書寫判斷條件啦，就是我們需要去思考什麼時候返回我們正確的組合，以及停止函數的運行。

這時候呢我們就可以在雙循環中加入判斷條件，如果兩個整數的和爲目標值時，就對數組進行賦值，並返回，否則繼續循環

加入判斷條件

現在，我們已經完成大部分代碼了，加油，還差一點兒。我們的代碼是不是還少了些什麼？如果在兩個循環結束時都沒有找到和爲目標值的兩個整數，那麼我們這個函數是不是就會出錯，因爲這時候該函數沒有返回值了。

所以呢爲了解決這個問題，我們就可以在函數的末尾加入返回值，一個是表明返回0個整數的整形指針，一個是NULL代表沒有返回值，也就是沒有找到目標組合

循環結束後的返回值

最終代碼如下

最終代碼

因爲在該算法中需要進行雙重循環遍歷，所以時間複雜度爲O(n^2)，又因爲該代碼運行過程中所需的額外存儲空間是固定的，與輸入數據的規模無關，所以空間複雜度爲O(1)。

在 C 語言中，指針的算術運算（如 + -）是基於指針所指向的數據類型大小的，而不是直接操作字節數。

接下來呢，還存在第二種方法。

就是以空間換時間，建立哈希表，將已經遍歷的元素存入，後續遍歷的元素到哈希表中尋找是否存在匹配的元素，若存在返回，若不存在也存入哈希表後繼續遍歷，直置有返回或遍歷結束。

第二種因爲需要應用到哈希表，會在後序的題目中進行詳細的講解，故在此便不展開哩。

使用該方法的時間空間複雜度均爲O(n)。

好了，這道題目就到此結束啦，有什麼問題和疑問呢歡迎熱心的盒友們提出啊。