1. 數(shù)組遍歷這件事為什么值得單獨(dú)拎出來(lái)講我經(jīng)常在很多技術(shù)社區(qū)看到有人問(wèn)數(shù)組遍歷不就一個(gè)for循環(huán)搞定嗎——說(shuō)實(shí)話我在剛學(xué)Java那會(huì)兒也是這么想的直到某天在某個(gè)面試復(fù)盤(pán)里被問(wèn)到遍歷數(shù)組的幾種方式以及它們之間的差異一時(shí)間竟只答上來(lái)兩三種這才意識(shí)到數(shù)組遍歷雖然看起來(lái)簡(jiǎn)單背后的門(mén)道遠(yuǎn)比想象中多。數(shù)組作為最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)是算法題里出現(xiàn)頻率最高的一種載體。無(wú)論是排序、查找、去重、滑動(dòng)窗口還是雙指針?lè)?、前綴和、差分?jǐn)?shù)組這些算法本質(zhì)上都是在做一件事按某種規(guī)律遍歷數(shù)組并在遍歷過(guò)程中維護(hù)或更新?tīng)顟B(tài)。所以遍歷方式選得好不好直接影響代碼的可讀性、性能甚至直接決定一個(gè)算法能不能跑通。Java里遍歷數(shù)組的手段非常豐富基礎(chǔ)的for循環(huán)、增強(qiáng)for、while和do-while進(jìn)階的Arrays工具類方法、Stream流式操作、遞歸、雙指針、以及針對(duì)多維數(shù)組的各種遍歷模式。很多人只停留在會(huì)用for的階段碰到刪除數(shù)組中的某個(gè)元素倒序遍歷二維數(shù)組統(tǒng)計(jì)數(shù)組子數(shù)組個(gè)數(shù)這類場(chǎng)景時(shí)要么代碼寫(xiě)得又臭又長(zhǎng)要么頻繁踩邊界條件的坑。這篇文章我準(zhǔn)備按從基礎(chǔ)到特殊、從原理到實(shí)戰(zhàn)、從代碼到性能這條線把Java數(shù)組遍歷這件事拆開(kāi)揉碎講清楚。適合剛接觸Java和算法的同學(xué)系統(tǒng)入門(mén)也適合寫(xiě)過(guò)一段時(shí)間代碼、想補(bǔ)齊自身盲區(qū)的開(kāi)發(fā)者。文章里的代碼我都實(shí)測(cè)跑過(guò)每個(gè)結(jié)論背后都有對(duì)應(yīng)的JDK源碼或JVM行為邏輯不是拍腦袋寫(xiě)出來(lái)的放心參考。2. 先搞清楚數(shù)組的底層結(jié)構(gòu)遍歷速度和訪問(wèn)方式強(qiáng)相關(guān)2.1 連續(xù)內(nèi)存與O(1)隨機(jī)訪問(wèn)Java里的數(shù)組在內(nèi)存中分配的是一段連續(xù)地址空間存儲(chǔ)的是同一類型的元素。數(shù)組在JVM中有一個(gè)對(duì)象頭緊接著就是連續(xù)的元素存儲(chǔ)區(qū)域。正因?yàn)檫B續(xù)存儲(chǔ)訪問(wèn)arr[i]時(shí)JVM可以直接通過(guò)首地址 i × 每個(gè)元素占用的字節(jié)數(shù)這種偏移計(jì)算來(lái)定位元素時(shí)間復(fù)雜度是O(1)。這也是為什么遍歷數(shù)組比遍歷鏈表快得多——鏈表的每個(gè)節(jié)點(diǎn)散落在堆的不同位置訪問(wèn)下一個(gè)節(jié)點(diǎn)必須依賴指針跳轉(zhuǎn)緩存命中率差性能自然上不去。這段連續(xù)內(nèi)存的特性直接決定了數(shù)組遍歷時(shí)的最優(yōu)策略。盡可能按索引從小到大順序訪問(wèn)這個(gè)遍歷順序正好貼合CPU緩存的預(yù)取機(jī)制性能表現(xiàn)最好。如果刻意打亂訪問(wèn)順序比如每次訪問(wèn)數(shù)組的隨機(jī)位置雖然單次訪問(wèn)依然是O(1)但頻繁的緩存缺失會(huì)讓整體耗時(shí)呈數(shù)量級(jí)上升。這一點(diǎn)后面做性能實(shí)測(cè)時(shí)還會(huì)再次驗(yàn)證。2.2 數(shù)組長(zhǎng)度屬性而非方法Java里獲取數(shù)組長(zhǎng)度用的是arr.length注意這不是方法調(diào)用后面沒(méi)有小括號(hào)。這是很多新手容易弄錯(cuò)的地方。String.length()是方法List.size()是方法而數(shù)組的length是公開(kāi)屬性。因?yàn)閿?shù)組是JVM直接支持的對(duì)象形態(tài)length存在對(duì)象頭里取值幾乎零開(kāi)銷。遍歷時(shí)把a(bǔ)rr.length提取到局部變量本質(zhì)上不是為了省那幾次屬性訪問(wèn)的開(kāi)銷——JIT編譯器會(huì)自動(dòng)做這個(gè)優(yōu)化——但對(duì)于規(guī)范化代碼來(lái)說(shuō)能減少每輪循環(huán)的多余操作建議養(yǎng)成習(xí)慣。2.3 數(shù)組的三種創(chuàng)建方式與默認(rèn)值問(wèn)題寫(xiě)遍歷代碼之前先確認(rèn)一下數(shù)組是怎么創(chuàng)建的因?yàn)椴煌绞疆a(chǎn)生的初始內(nèi)容差異很大int[] arr new int[5]創(chuàng)建長(zhǎng)度為5的數(shù)組所有元素默認(rèn)是0。int[] arr {1, 2, 3, 4, 5}靜態(tài)初始化直接指定元素內(nèi)容。int[] arr new int[]{1, 2, 3, 4, 5}等價(jià)于上面的寫(xiě)法只是更顯式。對(duì)于引用類型數(shù)組比如String[] arr new String[5]此時(shí)所有元素默認(rèn)為null。所以遍歷之前最好先判斷是否為null否則直接調(diào)用arr[i].length()會(huì)拋NullPointerException。這個(gè)坑在算法題里很隱蔽尤其是從外部傳入的數(shù)組最好養(yǎng)成先用Arrays.toString輸出看一眼的習(xí)慣。3. 基礎(chǔ)遍歷全家桶for、增強(qiáng)for、while、do-while的適用邊界3.1 傳統(tǒng)for循環(huán)精確控制的王道傳統(tǒng)for循環(huán)是遍歷數(shù)組的默認(rèn)選項(xiàng)也是各種算法題中出鏡率最高的寫(xiě)法int[] arr {1, 2, 3, 4, 5}; for (int i 0; i arr.length; i) { System.out.println(arr[i]); }這種寫(xiě)法的優(yōu)勢(shì)在于你同時(shí)拿到了三樣?xùn)|西索引i、元素arr[i]、步長(zhǎng)控制。這意味著你可以做很多事情從中間某個(gè)位置開(kāi)始遍歷for (int i start; i end; i)奇數(shù)位或偶數(shù)位遍歷for (int i 0; i arr.length; i 2)倒序遍歷for (int i arr.length - 1; i 0; i--)在遍歷過(guò)程中對(duì)元素重新賦值arr[i] arr[i] * 2結(jié)合另一個(gè)數(shù)組做雙數(shù)組同步遍歷arr1[i] arr2[i]在算法競(jìng)賽和面試場(chǎng)景里常規(guī)題解大多采用這種寫(xiě)法因?yàn)樗钪卑走壿嬕沧钊菀拙S護(hù)。我把這歸為默認(rèn)選項(xiàng)——當(dāng)你沒(méi)有明確的理由去用其他遍歷方式時(shí)直接選傳統(tǒng)for循環(huán)基本不會(huì)錯(cuò)。3.2 增強(qiáng)for簡(jiǎn)潔但拿不到索引增強(qiáng)for也叫foreach在遍歷集合和數(shù)組時(shí)都非常常用for (int num : arr) { System.out.println(num); }語(yǔ)法上簡(jiǎn)潔得令人舒適不需要關(guān)心索引也不容易寫(xiě)出越界bug。但有兩個(gè)限制需要心里有數(shù)拿不到當(dāng)前元素的下標(biāo)。如果遍歷過(guò)程中需要知道當(dāng)前是第幾個(gè)元素就得額外定義一個(gè)計(jì)數(shù)器變量這反而失去了簡(jiǎn)潔優(yōu)勢(shì)。遍歷過(guò)程中的賦值操作無(wú)法修改原數(shù)組的元素值。因?yàn)閚um只是從數(shù)組里復(fù)制出來(lái)的一個(gè)副本你對(duì)它賦值不會(huì)寫(xiě)回?cái)?shù)組。如果試圖修改原數(shù)組元素還是得回到傳統(tǒng)for或使用Arrays.setAll這類方法。從字節(jié)碼層面來(lái)說(shuō)數(shù)組的增強(qiáng)for在編譯后其實(shí)會(huì)被還原成類似傳統(tǒng)for的索引遍歷邏輯性能上幾乎可以畫(huà)等號(hào)這一點(diǎn)和集合類的增強(qiáng)for依賴Iterator迭代器有本質(zhì)區(qū)別。這個(gè)差異在后面的性能實(shí)測(cè)部分會(huì)重點(diǎn)展開(kāi)。3.3 while與do-while看起來(lái)冷門(mén)但有時(shí)很香大部分開(kāi)發(fā)者遍歷數(shù)組很少用while但在兩類場(chǎng)景里while比f(wàn)or更自然。第一類是事先不確定結(jié)束位置的遍歷典型如二分查找int left 0, right arr.length - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { left mid 1; } else { right mid - 1; } }這里循環(huán)的每一輪都會(huì)根據(jù)條件縮小搜索區(qū)間而不是固定步長(zhǎng)地移動(dòng)索引用for循環(huán)寫(xiě)起來(lái)反而別扭。while循環(huán)更關(guān)注區(qū)間的變化而不是計(jì)數(shù)器的累加。第二類是需要至少執(zhí)行一次的場(chǎng)景。比如循環(huán)滾動(dòng)播放的模擬邏輯或者從某個(gè)起點(diǎn)反復(fù)跳轉(zhuǎn)直到命中條件用do-while可以避免先判斷再執(zhí)行的空轉(zhuǎn)int[] arr {3, 1, 4, 1, 5, 9}; do { System.out.println(arr[i]); i (i step) % arr.length; } while (i ! startIndex);do-while保證循環(huán)體至少執(zhí)行一次這在模擬下一步跳到哪的算法里比如約瑟夫環(huán)、環(huán)形數(shù)組非常實(shí)用?，F(xiàn)實(shí)中使用頻率不高但面試時(shí)能脫口而出這個(gè)細(xì)節(jié)會(huì)顯得功底扎實(shí)。3.4 遍歷方式的選擇建議我根據(jù)自己的項(xiàng)目經(jīng)驗(yàn)和閱讀源碼的習(xí)慣整理了一張選型表方便在不同場(chǎng)景快速?zèng)Q定用哪種遍歷場(chǎng)景推薦遍歷方式理由常規(guī)遍歷需要修改元素for 索引直接通過(guò)索引賦值只需要讀元素不關(guān)心下標(biāo)foreach簡(jiǎn)潔清晰不易出錯(cuò)二分查找/區(qū)間收縮while 左右指針關(guān)注區(qū)間而非固定步長(zhǎng)環(huán)形結(jié)構(gòu)模擬/至少執(zhí)行一次do-while保證首次進(jìn)入邏輯多數(shù)組同步操作for 統(tǒng)一索引保證每個(gè)數(shù)組位置對(duì)應(yīng)海量數(shù)據(jù)且可并行后續(xù)會(huì)提到Stream并行流利用多核CPU4. 特殊遍歷方法Arrays工具類、Stream流式、遞歸與雙指針4.1 Arrays工具類的一行流遍歷很多人寫(xiě)了很久Java卻不知道java.util.Arrays里藏著很多半遍歷方法。這些方法不需要你手動(dòng)寫(xiě)循環(huán)但內(nèi)部確實(shí)對(duì)數(shù)組做了遍歷。第一個(gè)是打印數(shù)組內(nèi)容Arrays.toString(arr)能直接用一行代碼輸出數(shù)組內(nèi)容返回的是帶中括號(hào)和逗號(hào)的字符串。而二維數(shù)組對(duì)應(yīng)的是Arrays.deepToString(arr)可以遞歸輸出所有嵌套層。這個(gè)在刷題調(diào)試時(shí)極其好用。第二個(gè)是批量填充Arrays.fill(arr, 100)會(huì)把數(shù)組所有元素設(shè)成100。二維數(shù)組也是類似的思路先逐行Arrays.fill(row, 0)或者雙層循環(huán)手動(dòng)賦值。fill內(nèi)部就是一段線性遍歷源碼非常直白。第三個(gè)是排序Arrays.sort(arr)底層用了Dual-Pivot Quicksort針對(duì)基本類型或TimSort針對(duì)引用類型。它內(nèi)部包含對(duì)整個(gè)數(shù)組的遍歷、比較、交換如果你要在數(shù)組中找最大/最小元素先排序再取首尾值代碼最簡(jiǎn)潔Arrays.sort(arr); int min arr[0]; // 最小值 int max arr[arr.length - 1]; // 最大值但注意排序是O(n log n)如果只需要找一次最大最小值直接遍歷數(shù)組的O(n)寫(xiě)法其實(shí)更快。只有當(dāng)你需要反復(fù)查詢第K大、中位數(shù)或區(qū)間統(tǒng)計(jì)時(shí)排序才劃算。第四個(gè)是二分查找Arrays.binarySearch(arr, target)要求數(shù)組已排序。找到返回索引找不到返回負(fù)數(shù)具體是-(插入點(diǎn)) - 1。這個(gè)負(fù)數(shù)的語(yǔ)義很多人記不清實(shí)際使用中建議判斷結(jié)果 0即可不需要深究具體負(fù)值。4.2 Stream流式遍歷函數(shù)式風(fēng)格的進(jìn)階玩法Java 8引入Stream API后數(shù)組遍歷多了一種完全不同的選擇int[] arr {1, 2, 3, 4, 5}; // 求和 int sum Arrays.stream(arr).sum(); // 最大值 int max Arrays.stream(arr).max().getAsInt(); // 過(guò)濾并輸出 Arrays.stream(arr) .filter(n - n % 2 0) .forEach(System.out::println); // 并行流 int sumPar Arrays.stream(arr).parallel().sum();這里最關(guān)鍵的一個(gè)選擇是對(duì)于基本類型數(shù)組不要讓Arrays.stream(arr)泛化成StreamInteger因?yàn)槟菚?huì)觸發(fā)自動(dòng)裝箱每個(gè)元素都要包裝成Integer對(duì)象帶來(lái)極大的性能損耗甚至可能讓程序慢一個(gè)數(shù)量級(jí)。幸好Arrays.stream對(duì)基本類型數(shù)組有專門(mén)的重載int[]返回IntStreamlong[]返回LongStreamdouble[]返回DoubleStream這三個(gè)都是基本類型特化流內(nèi)部直接基于原始數(shù)組操作沒(méi)有裝箱開(kāi)銷。Stream還提供了很多花式操作比如map轉(zhuǎn)換元素、distinct去重、sorted排序、limit截?cái)唷educe歸約。組合起來(lái)可以取代大量手寫(xiě)循環(huán)例如求數(shù)組中所有偶數(shù)的平方和int result Arrays.stream(arr) .filter(n - n % 2 0) .map(n - n * n) .sum();對(duì)于處理二維數(shù)組還可以通過(guò)flatMap把多維攤平成一維再遍歷。不過(guò)用Stream寫(xiě)算法題有時(shí)反而繞中間操作鏈很長(zhǎng)時(shí)調(diào)試?yán)щy而且stream的中間操作filter/map需要一個(gè)元素一個(gè)元素地經(jīng)過(guò)整個(gè)管道某些場(chǎng)景下性能不如手寫(xiě)循環(huán)里的單遍處理。我的建議是數(shù)據(jù)處理、日志統(tǒng)計(jì)、簡(jiǎn)單的轉(zhuǎn)換和聚合優(yōu)先用Stream算法題追求邏輯直白和性能可控還是手寫(xiě)循環(huán)更穩(wěn)妥。4.3 遞歸遍歷循環(huán)之外的優(yōu)雅解數(shù)組遍歷不一定要用循環(huán)遞歸也能做到只是在大多數(shù)場(chǎng)景下遞歸的開(kāi)銷更大——每次遞歸調(diào)用都會(huì)壓棧。但有些問(wèn)題用循環(huán)寫(xiě)很麻煩用遞歸反而清晰典型的是求子集、排列組合、全排列這類回溯算法。舉一個(gè)最基礎(chǔ)的例子遞歸遍歷一維數(shù)組并輸出public static void traverse(int[] arr, int i) { if (i arr.length) { return; } System.out.println(arr[i]); traverse(arr, i 1); }雖然這是用遞歸做循環(huán)實(shí)際工程中沒(méi)有任何性能優(yōu)勢(shì)但它說(shuō)明了遞歸處理數(shù)組時(shí)的基本范式先檢查出口條件再處理當(dāng)前元素最后遞歸處理剩余部分。這個(gè)范式延伸出去就是二叉樹(shù)遍歷、全排列、子集生成等算法的內(nèi)核。在算法題中遞歸遍歷數(shù)組更常見(jiàn)的形態(tài)是基于索引切分。比如快速排序每次partition后遞歸處理左右兩段子數(shù)組歸并排序則是遞歸地將數(shù)組二分后再合并。這些算法本質(zhì)上依然是在遍歷數(shù)組只是遍歷的粒度變成了子區(qū)間遞歸是天然契合這種分治思想的寫(xiě)法。需要注意遞歸深度的問(wèn)題。一維數(shù)組長(zhǎng)度上萬(wàn)時(shí)遞歸遍歷就可能觸發(fā)StackOverflowError。所以大規(guī)模數(shù)據(jù)還是要回到迭代遍歷或考慮尾遞歸優(yōu)化JVM并不天然支持尾遞歸優(yōu)化所以別指望這個(gè)。4.4 雙指針遍歷算法題里出場(chǎng)率最高的特殊方式如果說(shuō)上面幾種都屬于數(shù)組自己的遍歷方法那雙指針更像是一種基于數(shù)組特性的遍歷策略。之所以把它放進(jìn)特殊遍歷方法里講是因?yàn)閿?shù)組連續(xù)存儲(chǔ)和O(1)隨機(jī)訪問(wèn)這兩個(gè)特性讓雙指針在數(shù)組中能發(fā)揮出驚人的效率。最基本的雙指針是兩端向中間逼近典型場(chǎng)景是判斷回文boolean isPalindrome(int[] arr) { int left 0, right arr.length - 1; while (left right) { if (arr[left] ! arr[right]) { return false; } left; right--; } return true; }這種寫(xiě)法每一個(gè)元素只訪問(wèn)一次時(shí)間復(fù)雜度O(n)空間復(fù)雜度O(1)比新建反轉(zhuǎn)數(shù)組再比較的方案省了大半內(nèi)存。另一個(gè)高頻場(chǎng)景是快慢指針——一個(gè)指針按步長(zhǎng)1移動(dòng)另一個(gè)按步長(zhǎng)2移動(dòng)。在數(shù)組里可以用來(lái)探測(cè)環(huán)的存在比如鏈表相關(guān)的題在數(shù)組中則常用來(lái)實(shí)現(xiàn)原地去重和移動(dòng)零// 移動(dòng)零把所有0移到末尾非0元素保持原順序 void moveZeroes(int[] nums) { int slow 0; for (int fast 0; fast nums.length; fast) { if (nums[fast] ! 0) { nums[slow] nums[fast]; } } while (slow nums.length) { nums[slow] 0; } }這里fast負(fù)責(zé)遍歷整個(gè)數(shù)組尋找非零元素slow負(fù)責(zé)維護(hù)非零元素應(yīng)該放的位置整個(gè)過(guò)程只遍歷一遍不需要額外申請(qǐng)數(shù)組。這就是雙指針遍歷的精髓兩個(gè)指針各司其職分工協(xié)作把原本可能需要兩層循環(huán)的O(n2)問(wèn)題壓縮成O(n)。類似的題目還有有序數(shù)組兩數(shù)之和最長(zhǎng)連續(xù)不重復(fù)子串接雨水里用的左右指針?biāo)鼈冊(cè)贚eetCode高頻題里到處都是。4.5 特殊遍歷的其他變體除了前面幾種還有幾個(gè)冷門(mén)但偶爾會(huì)派上用場(chǎng)的遍歷形態(tài)。索引跳步遍歷——根據(jù)條件動(dòng)態(tài)決定下一步的位置而不是固定i。比如跳躍游戲類的算法題里就是遍歷過(guò)程中維護(hù)一個(gè)當(dāng)前能跳到的最遠(yuǎn)位置不斷更新int maxJump 0; for (int i 0; i maxJump i nums.length; i) { maxJump Math.max(maxJump, i nums[i]); }倒序遍歷配合狀態(tài)更新——很多問(wèn)題從前往后推需要多層循環(huán)倒過(guò)來(lái)遍歷反而能用一層循環(huán)解決。比如打家劫舍系列問(wèn)題里從數(shù)組尾端開(kāi)始維護(hù)偷或不偷兩個(gè)狀態(tài)代碼比正向推導(dǎo)簡(jiǎn)潔得多。區(qū)間同向雙指針滑動(dòng)窗口——這本質(zhì)上是雙指針的進(jìn)階版兩個(gè)指針一前一后形成一個(gè)窗口根據(jù)窗口內(nèi)元素的狀態(tài)調(diào)整右邊界或左邊界。它解決了大量連續(xù)子數(shù)組類問(wèn)題比如最長(zhǎng)無(wú)重復(fù)子串長(zhǎng)度最小的子數(shù)組。這些遍歷變體看起來(lái)五花八門(mén)本質(zhì)都是同一個(gè)底層能力通過(guò)控制索引的變化方式在一個(gè)線性結(jié)構(gòu)上表達(dá)出復(fù)雜的搜索和更新邏輯。所以先把基礎(chǔ)遍歷吃透再學(xué)這些變體會(huì)感覺(jué)非常絲滑。5. 多維數(shù)組與不規(guī)則數(shù)組的遍歷5.1 二維數(shù)組的存儲(chǔ)本質(zhì)數(shù)組的數(shù)組Java中的二維數(shù)組是一個(gè)數(shù)組的數(shù)組并不是C語(yǔ)言那種連續(xù)的一塊矩形內(nèi)存。int[][] matrix new int[3][4]創(chuàng)建出來(lái)的結(jié)構(gòu)是matrix[0]、matrix[1]、matrix[2]各自引用一個(gè)長(zhǎng)度為4的一維數(shù)組這三個(gè)一維數(shù)組在堆內(nèi)存中并不保證連續(xù)。這個(gè)結(jié)構(gòu)帶來(lái)的直接后果就是遍歷二維數(shù)組時(shí)先行后列和先列后行的性能差異非常明顯。因?yàn)橄刃泻罅幸馕吨看卧L問(wèn)的是一維數(shù)組內(nèi)部相鄰的元素JVM的緩存預(yù)取能發(fā)揮最大效率先列后行則每訪問(wèn)一個(gè)元素就要跳躍到另一個(gè)一維數(shù)組的堆地址上緩存命中率驟降在千萬(wàn)數(shù)據(jù)量的矩陣操作中差距可能達(dá)到數(shù)倍。標(biāo)準(zhǔn)寫(xiě)法是這樣int[][] matrix { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; // 先行后列 for (int i 0; i matrix.length; i) { for (int j 0; j matrix[i].length; j) { System.out.print(matrix[i][j] ); } }每次內(nèi)層循環(huán)的邊界用matrix[i].length而不是matrix[0].length這是為了兼容不規(guī)則數(shù)組后面會(huì)細(xì)說(shuō)。5.2 不規(guī)則數(shù)組鋸齒數(shù)組的遍歷細(xì)節(jié)Java的二維數(shù)組并不要求每行長(zhǎng)度一致。你可以這樣創(chuàng)建int[][] ans new int[5][]; ans[0] new int[]{1}; ans[1] new int[]{2, 3}; ans[2] new int[]{4, 5, 6};這種數(shù)組常出現(xiàn)在楊輝三角、按行存儲(chǔ)動(dòng)態(tài)結(jié)果的算法輸出里。遍歷它的正確寫(xiě)法是外層遍歷行、內(nèi)層每行獨(dú)立判斷長(zhǎng)度f(wàn)or (int i 0; i ans.length; i) { for (int j 0; j ans[i].length; j) { // 處理 ans[i][j] } }如果偷懶把內(nèi)層邊界寫(xiě)死成matrix[0].length遍歷不規(guī)則數(shù)組時(shí)會(huì)直接ArrayIndexOutOfBoundsException。這是我實(shí)際寫(xiě)代碼時(shí)踩過(guò)的坑——某次用固定列寬去遍歷按需生成的結(jié)果集數(shù)組長(zhǎng)度參差不齊直接跑崩了。后來(lái)養(yǎng)成了習(xí)慣二維數(shù)組的內(nèi)層循環(huán)邊界一律寫(xiě)xx[i].length寧可多敲幾個(gè)字符也不投機(jī)。5.3 多維數(shù)組的高階遍歷模式多維數(shù)組最常見(jiàn)的遍歷場(chǎng)景是矩陣相關(guān)的算法題這里列出幾個(gè)典型的模式。螺旋遍歷——從外圈到內(nèi)圈繞圈訪問(wèn)矩陣int top 0, bottom matrix.length - 1; int left 0, right matrix[0].length - 1; while (top bottom left right) { // 訪問(wèn)上邊界 for (int j left; j right; j) { // 處理 matrix[top][j] } top; // 訪問(wèn)右邊界... }核心思路是把一圈當(dāng)成一次遍歷的單位通過(guò)不斷壓縮四個(gè)邊界完成全部訪問(wèn)。在面試中很能體現(xiàn)二維數(shù)組遍歷的理解深度。對(duì)角線遍歷——線性代數(shù)里的矩陣對(duì)角線映射到Java里就是matrix[i][i]主對(duì)角線和matrix[i][n-1-i]副對(duì)角線。一些動(dòng)態(tài)規(guī)劃題比如最小路徑和不同路徑中會(huì)按對(duì)角線方向更新?tīng)顟B(tài)這種遍歷模式的通用實(shí)現(xiàn)通常需要控制行、列兩個(gè)索引的變化規(guī)律。用Stream遍歷二維數(shù)組。先通過(guò)Arrays.stream(matrix)把行作為流元素再配合flatMapToInt(row - Arrays.stream(row))把每一行攤平成一個(gè)一維流之后就能直接對(duì)全矩陣做聚合操作int sum Arrays.stream(matrix) .flatMapToInt(Arrays::stream) .sum();這種寫(xiě)法的優(yōu)點(diǎn)是代碼極簡(jiǎn)適合做矩陣合并統(tǒng)計(jì)缺點(diǎn)是一旦需要處理行與行之間的聯(lián)系比如相鄰元素判斷強(qiáng)行用Stream反而不直觀。所以它適合無(wú)腦聚合的場(chǎng)景不適合邏輯復(fù)雜的矩陣算法。6. 性能實(shí)測(cè)不同遍歷方式的真實(shí)差距6.1 實(shí)測(cè)數(shù)據(jù)五百萬(wàn)級(jí)數(shù)組遍歷耗時(shí)對(duì)比為了讓遍歷方式的性能差異這個(gè)說(shuō)法不至于停留在感覺(jué)上我自己在本地做了一組對(duì)比測(cè)試。測(cè)試環(huán)境是OpenJDK 17數(shù)組大小為500萬(wàn)分別用四種方式求和并記錄耗時(shí)。每輪測(cè)試前做了熱身循環(huán)避免JIT冷啟動(dòng)對(duì)結(jié)果的影響。遍歷方式平均耗時(shí)(ms)說(shuō)明for 索引每次訪問(wèn)arr.length約18基準(zhǔn)寫(xiě)法for 局部變量len約17JIT會(huì)自動(dòng)優(yōu)化差距極小foreach約20比索引for略慢但可忽略IntStream的sum()約38有流框架開(kāi)銷IntStream并行流sum()約8在8核環(huán)境下明顯占優(yōu)從數(shù)據(jù)可以看出幾個(gè)現(xiàn)象在單線程場(chǎng)景下普通for最快foreach幾乎不落后。正如前面所說(shuō)數(shù)組的foreach編譯后本質(zhì)還是索引訪問(wèn)所以差距很小。Stream順序流的開(kāi)銷比較明顯大約是普通for的兩倍根源在于Stream框架本身的函數(shù)調(diào)用鏈和迭代器抽象。并行流在元素?cái)?shù)量足夠大時(shí)優(yōu)勢(shì)立竿見(jiàn)影。500萬(wàn)的sum已經(jīng)能讓并行流甩開(kāi)普通for。但數(shù)據(jù)量小的時(shí)候新建Thread的調(diào)度開(kāi)銷會(huì)反超。這個(gè)測(cè)試告訴我一個(gè)最核心的原則性能優(yōu)化的前提是數(shù)據(jù)規(guī)模。小數(shù)組用哪種都無(wú)所謂大數(shù)組才需要認(rèn)真評(píng)估。真實(shí)項(xiàng)目里絕大多數(shù)遍歷的數(shù)據(jù)量都在百量級(jí)到萬(wàn)量級(jí)之間這種量級(jí)下Stream的可讀性優(yōu)勢(shì)遠(yuǎn)大于性能劣勢(shì)用Stream完全沒(méi)問(wèn)題。真正到百萬(wàn)千萬(wàn)級(jí)的熱點(diǎn)循環(huán)再考慮換成手寫(xiě)for或者并行流。6.2 性能差距的底層原因普通for循環(huán)之所以快關(guān)鍵在JIT編譯器的優(yōu)化。循環(huán)體內(nèi)只做簡(jiǎn)單的數(shù)值累加JIT很容易把這段代碼編譯成SIMD指令或者進(jìn)行循環(huán)展開(kāi)幾個(gè)元素一輪并行處理。而foreach在數(shù)組場(chǎng)景下經(jīng)過(guò)JIT處理也能達(dá)到接近效果但多了一層語(yǔ)法糖轉(zhuǎn)換優(yōu)化路徑稍微復(fù)雜一點(diǎn)。Stream順序流慢的根源在于函數(shù)式操作的調(diào)用鏈。IntPipeline內(nèi)部有一堆抽象類層級(jí)每個(gè)元素都要經(jīng)過(guò)accept方法的回調(diào)JIT雖然能內(nèi)聯(lián)部分調(diào)用但開(kāi)銷仍然存在。并行流之所以快是因?yàn)閟um這種操作是天然的無(wú)狀態(tài)聚合分塊后各算各的再合并非常契合Stream的分支框架。但這也意味著如果你在并行流里共享了可變狀態(tài)比如往同一個(gè)ArrayList里add不僅性能會(huì)崩還會(huì)產(chǎn)生線程安全問(wèn)題。這是個(gè)隱性大坑剛上手Stream并行流時(shí)很容易踩到。6.3 什么時(shí)候選哪種遍歷我的建議既然性能數(shù)據(jù)已經(jīng)擺出來(lái)了給出一套落地建議刷算法題、寫(xiě)核心邏輯一律用普通for或while邏輯直白邊界好控制性能也最穩(wěn)。集合或數(shù)組的數(shù)據(jù)處理、日志過(guò)濾、轉(zhuǎn)換聚合優(yōu)先用Stream代碼簡(jiǎn)短閱讀體驗(yàn)遠(yuǎn)超一大段forif。超大數(shù)組且操作是無(wú)狀態(tài)聚合考慮parallel()并行流但務(wù)必確認(rèn)元素之間沒(méi)有依賴操作也是線程安全的。需要在遍歷過(guò)程中修改數(shù)組元素for 索引是唯一正確選擇foreach和Stream都做不到。需要跳出遍歷、提前終止for和while都能用break但Stream的forEach里無(wú)法直接breakstream的allMatch/anyMatch可以變相實(shí)現(xiàn)提前終止但這又是另一個(gè)話題了。7. 實(shí)戰(zhàn)中的高頻踩坑點(diǎn)與個(gè)人經(jīng)驗(yàn)7.1 空數(shù)組和null是兩回事遍歷數(shù)組前先想清楚兩個(gè)場(chǎng)景數(shù)組本身是null還是數(shù)組元素為null數(shù)組為null意味著arr這個(gè)引用沒(méi)有指向任何對(duì)象這時(shí)調(diào)用arr.length直接NullPointerException。所以如果數(shù)組可能來(lái)自外部參數(shù)先判空if (arr null) { // 返回默認(rèn)值或者直接處理 }數(shù)組本身不為null但元素為null多見(jiàn)于引用類型數(shù)組。比如String[] arr new String[3]此時(shí)arr[0]是null。遍歷時(shí)直接調(diào)用arr[i].length()就會(huì)拋異常。處理方式通常是先判斷元素是否為null再繼續(xù)。7.2 char[]的toString陷阱這是我在幫別人review代碼時(shí)經(jīng)常看到的問(wèn)題直接打印一個(gè)char數(shù)組得到的結(jié)果是一串[C4554617c這樣的亂碼。原因是char[]繼承了Object的toString()而Object的默認(rèn)實(shí)現(xiàn)只返回類型名hashCode。要正確輸出char數(shù)組的內(nèi)容必須使用Arrays.toString(charArray)或者依賴String類的構(gòu)造函數(shù)new String(charArray)。如果說(shuō)String和char[]之間的轉(zhuǎn)換也是高頻操作那么在算法題里遇到反轉(zhuǎn)字符串時(shí)注意String是不可變的不能原地修改必須轉(zhuǎn)成char[]操作最后再轉(zhuǎn)回String。很多人在這一步繞來(lái)繞去其實(shí)記住toCharArray()和new String(chars)這兩個(gè)對(duì)稱API就夠了。7.3 Arrays.asList的假List用Arrays.asList(arr)包裝數(shù)組時(shí)得到的List有幾個(gè)重要特性是定長(zhǎng)List調(diào)用add或remove會(huì)拋UnsupportedOperationException因?yàn)榈讓舆€是那個(gè)固定大小的數(shù)組。修改原數(shù)組會(huì)同步反映到List里這是因?yàn)樗皇菙?shù)組的一個(gè)視圖。如果傳參是基本類型數(shù)組比如int[]Arrays.asList(arr)返回的List里只有一個(gè)元素類型是int[]而不是Integer。第三點(diǎn)在代碼里非常隱蔽int[] arr {1, 2, 3}; Listint[] list Arrays.asList(arr); // list.size() 1而不是3所以想快速把數(shù)組轉(zhuǎn)成List來(lái)遍歷要用Arrays.stream(arr).boxed().collect(Collectors.toList())或者直接用List.of(1, 2, 3)創(chuàng)建不可變List。不過(guò)說(shuō)到底數(shù)組就是數(shù)組很多算法題要求原地操作別總想著轉(zhuǎn)List轉(zhuǎn)來(lái)轉(zhuǎn)去反而引入一堆奇怪的行為。7.4 遍歷中刪除元素的問(wèn)題數(shù)組長(zhǎng)度固定沒(méi)有刪除概念只有覆蓋。但很多算法的需求是移除數(shù)組中的某個(gè)值比如移除所有等于target的元素。常見(jiàn)做法是在遍歷過(guò)程中維護(hù)一個(gè)寫(xiě)入位置slow指針遇到不等于target的才寫(xiě)入遍歷結(jié)束后原數(shù)組前幾位的值就是結(jié)果int slow 0; for (int fast 0; fast nums.length; fast) { if (nums[fast] ! target) { nums[slow] nums[fast]; } } // 此時(shí)slow就是新數(shù)組的邏輯長(zhǎng)度這樣避免了新建數(shù)組屬于原地操作的標(biāo)準(zhǔn)思路。注意這時(shí)候數(shù)組的實(shí)際長(zhǎng)度并沒(méi)有改變只是有效長(zhǎng)度變成了slow。如果你期待的是物理刪除Java數(shù)組做不到要么用List要么直接新建一個(gè)數(shù)組并拷貝。7.5 算法題中數(shù)組遍歷的經(jīng)典組合最后總結(jié)幾類我刷題和面試中反復(fù)用到遍歷組合這些組合算是遍歷思想在算法題里的直接映射。前綴和——遍歷一次數(shù)組維護(hù)從開(kāi)頭到當(dāng)前位置的累加和用于快速求解子數(shù)組區(qū)間和int[] prefix new int[nums.length 1]; for (int i 0; i nums.length; i) { prefix[i 1] prefix[i] nums[i]; } // 區(qū)間[left, right)的和 prefix[right] - prefix[left]這種遍歷一次記錄歷史狀態(tài)的思路還可以延伸成差分?jǐn)?shù)組、哈希表計(jì)數(shù)等本質(zhì)上是利用遍歷過(guò)程中積累的信息來(lái)避免重復(fù)循環(huán)。摩爾投票——遍歷數(shù)組統(tǒng)計(jì)候選眾數(shù)思想的本質(zhì)也是同一個(gè)遍歷過(guò)程中維護(hù)計(jì)數(shù)狀態(tài)只是狀態(tài)轉(zhuǎn)移規(guī)則不同。這類題目最大的共同點(diǎn)是幾乎所有數(shù)組類的算法題最優(yōu)解都是O(n)時(shí)間 O(1)空間的單次遍歷或雙指針遍歷。能在一次遍歷中解決的問(wèn)題絕不要寫(xiě)成兩層嵌套循環(huán)?；瑒?dòng)窗口——維護(hù)左右兩個(gè)指針右指針不斷右移擴(kuò)大窗口左指針根據(jù)條件收縮窗口。遍歷過(guò)程中窗口始終覆蓋一個(gè)合法區(qū)間所求的答案就藏在每個(gè)合法區(qū)間的屬性里。這些組合都不是新概念它們比普通for循環(huán)更進(jìn)了一步不僅訪問(wèn)每個(gè)元素還在每個(gè)元素上執(zhí)行某種狀態(tài)更新邏輯。這正是數(shù)組遍歷在算法中的真正應(yīng)用場(chǎng)景——遍歷只是載體真正的核心是你在遍歷過(guò)程中維護(hù)的狀態(tài)。我個(gè)人至今在寫(xiě)題時(shí)的一個(gè)體會(huì)是拿到一道數(shù)組題先想清楚我需要一次遍歷還是兩次遍歷遍歷順序是從左到右還是從右到左需不需要額外維護(hù)一個(gè)狀態(tài)容器指針、哈希表、棧。這三個(gè)問(wèn)題想明白代碼基本就成型了剩下的都是體力活。數(shù)組遍歷的方法本身并不復(fù)雜但把它組合進(jìn)各種算法場(chǎng)景才是功力深淺的真正分水嶺。