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