前言

這是本人第一次參加由Datawhale舉辦的組隊學(xué)習活動，這個活動每月一次，之前也一直關(guān)注，但未親身參與過，這次看到活動中有一項組隊刷LeetCode，恰逢本人正在準備考研復(fù)試機試，便欣然加入以求有所收獲和提升。

同時，這也是本人第一次在CSDN寫文章，希望在此記錄并向大家分享自己在學(xué)習過程中總結(jié)的知識和收獲的感悟，也可以在此和大家談?wù)撚龅降膯栴}，向諸位優(yōu)秀的CSDNer們學(xué)習，我們共同進步！

ε≡?(?>?<)? 一心向?qū)W

活動簡介

天池Leetcode基礎(chǔ)訓(xùn)練營
適合leetcode小白，同時也可以學(xué)習到一些數(shù)據(jù)結(jié)構(gòu)與算法的知識，適合初學(xué)者快速入門，需要一點點的編程基礎(chǔ)。
2022年2月14日-2022年3月10日
o 知識講解＋例題解析＋習題實踐，完整入門Leetcode刷題之旅
o 24天訓(xùn)練營助教陪你答疑解惑
o 排名/周賽拿證書，給你的簡歷履歷添磚加瓦

活動地址
https://tianchi.aliyun.com/specials/promotion/2-9?spm=5176.15228502.0.0.34c079bfkDKMxB

Datawhale組隊學(xué)習
Datawhale是一個活躍于高校的開源組織，每月舉辦的組隊學(xué)習活動致力于營造互促的學(xué)習氛圍和純粹的學(xué)習環(huán)境，提供開源免費的學(xué)習內(nèi)容和學(xué)習規(guī)劃，方便大家有監(jiān)督和無監(jiān)督學(xué)習，從而幫助到更多學(xué)習者成長。截止今日，Datawhale已經(jīng)開源50多門學(xué)習內(nèi)容，涉及編程、數(shù)據(jù)科學(xué)、cv、nlp、強化學(xué)習和推薦系統(tǒng)6大模塊，這源自每一個開源貢獻者的參與。

開源地址
https://github.com/datawhalechina/team-learning

Task01數(shù)組

知識點總結(jié)

數(shù)組的定義
數(shù)組是具有一定順序關(guān)系的若干對象組成的集合，組成數(shù)組的對象成為數(shù)組元素。
它可以存儲一個 固定大小 的 相同類型 元素的順序集合。
數(shù)組的元素也可以是數(shù)組，這樣就得到了多維數(shù)組。

數(shù)組的存儲
數(shù)組是由連續(xù)的內(nèi)存位置組成，即在物理存儲層面是使用一片連續(xù)的存儲空間。
最低的地址對應(yīng)第一個元素，最高的地址對應(yīng)最后一個元素。 即按順序連續(xù)存儲。
這樣的好處是我們可以利用索引對數(shù)組元素進行隨機存取，而不足則是數(shù)組空間固定，不易擴充或減少，容易造成溢出或空間浪費。

數(shù)組元素的訪問
數(shù)組的存儲按照行優(yōu)先（C、C++、C#）或列優(yōu)先（Forturn）的原則進行。
可以利用以下公式計算得到數(shù)組中任一下標所存元素的位置，當然在C語言中我們可以直接利用下標對數(shù)組元素進行訪問。（考研數(shù)據(jù)結(jié)構(gòu)里面還是比較喜歡考下面這種計算的）
以下數(shù)組聲明分別為 type a[n]; type a[m][n]; type a[m][n][l];

一維數(shù)組：Loc(a[i]) = Loc(a[0]) + i x c
二維數(shù)組：Loc(a[i][j]) = Loc(a[0][0]) + (i x n + j) x c
三維數(shù)組：Loc(a[i][j][k]) = Loc(a[0][0][0]) + (i x n x l + j x l + k) x c
以上公式中 c 即代表數(shù)組中單個元素大小，可以利用 sizeof(a[0]) 得到，也是數(shù)據(jù)類型type的大小

例題

Leetcode1 兩數(shù)之和
這是一道很簡單的題，很直接的思路就是暴力解法，利用二重循環(huán)窮舉數(shù)組中兩元素之和，找到滿足的兩元素返回下標即可，這樣解答的時間復(fù)雜度是O(N²)；
此外，可以將數(shù)組先排序，再分別從頭尾開始夾逼。
Leetcode的官方題解還提供了利用哈希表的解法，這樣可以將時間復(fù)雜度降低至O(N)。

Leetcode16 最接近的三數(shù)之和
這是一道中等難度的題，也可以用暴力解法求解，即考慮直接使用三重循環(huán)枚舉三元組，找出與目標值最接近的作為答案，但是時間復(fù)雜度將達到O(N³)；
Leetcode的官方題解中給出的解法是雙指針法，即首先將數(shù)組元素升序排列，假設(shè)數(shù)組的長度為 n，我們需要的答案由 a、b、c 三個數(shù)得到，可以先枚舉 a，它在數(shù)組中的位置為 i，然后在位置 [i+1,n) 的范圍內(nèi)利用雙指針法枚舉 b 和 c。具體為令指針 low 指向 i+1，即 b 的起始位置，另指針 high 指向 n-1，即 c 的起始位置；利用 a+b+c 與 target 比較的結(jié)果來更新答案，即若 a+b+c > target，就使low++，若a+b+c < target，就使high–，而當 a+b+c = target 時即可直接返回答案。

作業(yè)題

1 Leetcode27 移除元素
這道題看似很簡單，但在代碼實現(xiàn)時需要注意細節(jié)，且題目中還特別注明需要原地移除待刪元素，即使用O(1)的額外空間。
對于數(shù)組我們沒法像鏈表那樣直接刪除某個結(jié)點，只能用其他值來覆蓋待刪元素的原始值。同時為了讓數(shù)組中剩余元素都集中在數(shù)組前部，即需要對數(shù)組元素進行移動，如果按照這樣的思路，則每找到一個等于 val 的元素，都要將其后所有元素向前移動，即num[i]=num[i+1]，時間復(fù)雜度為O(N²)。
優(yōu)化的算法是，利用雙指針，讓 i 指向當前將要處理的元素，j 指向下一個將要賦值的位置。如果 i 指向的元素不等于 val，則是需要保留的元素，就將 i 指向的元素復(fù)制到 j 指向的位置，然后將 i 和 j 同時右移；如果 i 指向的元素等于 val，則需要被覆蓋，此時 i 不動，j 右移一位。當 i 遍歷完整個數(shù)組后，j 的值即為結(jié)果數(shù)組的長度。
以上算法實現(xiàn)如下，另，以上算法還可以繼續(xù)優(yōu)化，即利用頭尾雙指針，具體可參考Leetcode官方題解。

int removeElement(int* nums, int numsSize, int val){int j=0;for(int i=0; i<numsSize; i++){if(nums[i]!=val)nums[j++]=nums[i];} // printf("%d\n",j); // for(int i=0; i<j; i++) // printf("%d ",nums[i]);return j; }

2 Leetcode26 刪除有序數(shù)組中的重復(fù)項
這道題與上一題極為相似，這里的重復(fù)項其實即為上一題中的val，又因為數(shù)組有序，所以重復(fù)項必定是連續(xù)的。利用雙指針法，用 i 指向需保留的元素的存儲位置，用 j 當前遍歷元素的位置，當數(shù)組元素大于0時，數(shù)組中至少包含一個元素，因此 nums[0] 必定保留，所以從下標 1 開始刪除重復(fù)元素。當 j 遍歷到與保留元素不相等的元素時，即要保留，將其賦給 i，并將 i 和 j 向后移動；當 j 指向元素與 i 所指元素相等時，即為重復(fù)項，繼續(xù)向后移動 j。
注意，這里的 i 指向的是結(jié)果數(shù)組中最后一個元素的位置，因此結(jié)果數(shù)組實際長度為 i+1 。
Leetcode官方題解中解法與此相同，但其具體實現(xiàn)時時用 nums[j] 與 nums[j-1] 相比。

int removeDuplicates(int* nums, int numsSize){int i=0;for(int j=1; j<numsSize; j++){if(nums[i]!=nums[j])nums[++i]=nums[j];}return i+1; }

3 Leetcode15 三數(shù)之和
這道題與例題中的第2題也是大同小異，相信那道題看懂了的話，這道題的思路也會很透徹，我就不再贅述。
這里重點說一下用C語言的代碼實現(xiàn)，如果是使用C++，那么豐富的STL可以很方便的操作和存儲三元組，但是C語言則需要用到指針和內(nèi)存管理相關(guān)的知識。
相信很多初學(xué)C語言的同學(xué)看到提交代碼的函數(shù)頭已是一頭霧水，還好我不久前剛好看過這塊兒相關(guān)的內(nèi)容，還可以理解一部分，但是也有些不懂的地方，這里給大家推薦一下一本C語言學(xué)習手冊。

回到這道題，首先需要明確的是，我們的結(jié)果是由若干三元組組成的一個數(shù)組，即一個二維數(shù)組，其中每個元素為含有三個元素的一維數(shù)組。再看這個函數(shù)頭，
int** threeSum，該函數(shù)的返回值為結(jié)果二維數(shù)組的起始位置，即第一個三元組中第一個元素的位置；int* returnSize，表示一共有多少個三元組，需要在起始時賦值0，若不在第一行賦值便會報錯，原因位置，還請知曉的大佬指教；int** returnColumnSizes，表示二維數(shù)組中每個元素（即一維數(shù)組）的大小，可見他也是一個二重指針，具體原因我也不知。

再看內(nèi)存申請：

int** ret = (int**)malloc(sizeof(int*) * numsSize * numsSize); ret[*returnSize] = (int*)malloc(sizeof(int) * 3);

以上兩句分別是為作為結(jié)果的二維數(shù)組 ret 和 ret 中每新增的一個三元組 ret[*returnSize] 申請空間。
在C語言中數(shù)組名等同于起始地址，也就是說，數(shù)組名就是指向第一個成員的指針，所以 ret[] 就等同于* ret； 而 int** ret 就等同于int ret[][]，但是后者聲明方法需要指出二維數(shù)組的大小，且聲明后得到的內(nèi)存空間將無法再進行改變，所以需要使用前者來動態(tài)申請一片空間。

*returnColumnSizes = (int*)malloc(sizeof(int) * numsSize * numsSize); (*returnColumnSizes)[*returnSize] = 3;

至于這兩句，我也著實存在疑問，不懂為什么要這樣申請空間以及賦值，還請朋友們指點。

int cmp(const void* a, const void* b){return (*(int*)a - *(int*)b); } int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){*returnSize = 0;if(numsSize < 3)return NULL;qsort(nums, numsSize, sizeof(int), cmp);int** ret = (int**)malloc(sizeof(int*) * numsSize * numsSize);*returnColumnSizes = (int*)malloc(sizeof(int) * numsSize * numsSize);for(int i=0; nums[i] <= 0 && i<numsSize-2; i++){if(i > 0 && nums[i]==nums[i-1])continue;int low = i+1, high = numsSize-1;while(low < high){int sum = nums[i] + nums[low] + nums[high];if(sum == 0){ret[*returnSize] = (int*)malloc(sizeof(int) * 3);ret[*returnSize][0] = nums[i];ret[*returnSize][1] = nums[low];ret[*returnSize][2] = nums[high];(*returnColumnSizes)[*returnSize] = 3;(*returnSize)++;while(low < high && nums[low] == nums[++low]);while(low < high && nums[high] == nums[--high]);}else if(sum < 0) low++;else high--;}} // printf("%d\n", *returnSize);return ret; }

結(jié)語

第一次寫文章必然存在很多不足，以上內(nèi)容若有錯誤，還請朋友們多多指點；另外由于趕時間，寫的比較匆忙，算法也沒有做圖解，說的可以也不太清楚，而且還有些疑問自己也未解決，還請大家包涵。

總結(jié)

以上是生活随笔為你收集整理的Leetcode学习成长记：天池leetcode基础训练营Task01数组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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