使用 JavaScript 在 DSA 中進行陣列遍歷：從基礎知識到進階技術

陣列遍歷是資料結構和演算法（DSA）中每個開發人員都應該掌握的基本概念。在本綜合指南中，我們將探索在 JavaScript 中遍歷陣列的各種技術，從基本方法開始，逐步發展到更高階的方法。我們將涵蓋 20 個範例，範圍從簡單到高級，並包括 LeetCode 風格的問題來強化您的學習。

目錄

1. 陣列遍歷簡介
2. 基本數組遍歷
   • 範例 1：使用 for 迴圈
   • 範例 2：使用 while 迴圈
   • 範例 3：使用 do-while 迴圈
   • 範例4：反向遍歷
3. 現代 JavaScript 陣列方法
   • 範例 5：forEach 方法
   • 範例6：map方法
   • 範例7：過濾方法
   • 範例8：reduce方法
4. 中階遍歷技術
   • 範例9：兩指針技術
   • 範例10：滑動視窗
   • 範例 11：Kadane 演算法
   • 範例12：荷蘭國旗演算法
5. 高級遍歷技術
   • 範例13：遞歸遍歷
   • 範例 14：排序數組上的二分搜尋
   • 範例 15：合併兩個排序數組
   • 範例 16：快速選擇演算法
6. 專門的遍歷
   • 範例 17：遍歷 2D 陣列
   • 範例 18：螺旋矩陣遍歷
   • 範例 19：對角線遍歷
   • 範例 20：之字形遍歷
7. 性能考慮因素
8. LeetCode 練習題
9. 結論

1. 數組遍歷簡介

陣列遍歷是存取陣列中的每個元素來執行某種操作的過程。這是程式設計中的關鍵技能，構成了許多演算法和資料操作的基礎。在 JavaScript 中，陣列是通用的資料結構，提供多種方式來遍歷和操作資料。

2. 基本數組遍歷

我們先從陣列遍歷的基本方法開始。

範例 1：使用 for 迴圈

經典的 for 迴圈是遍歷陣列最常見的方法之一。

function sumArray(arr) {
    let sum = 0;
    for (let i = 0; i 



<p><strong>時間複雜度</strong>：O(n)，其中n是陣列的長度。 </p>

<p></p>

<h3>
  
  
  範例 2：使用 while 循環
</h3>

<p>while迴圈也可以用於陣列遍歷，特別是當終止條件比較複雜時。 <br>
</p>

<pre class="brush:php;toolbar:false">function findFirstNegative(arr) {
    let i = 0;
    while (i = 0) {
        i++;
    }
    return i 



<p><strong>時間複雜度</strong>：最壞情況下為 O(n)，但如果儘早發現負數，時間複雜度可能會更低。 </p>

<p></p>

<h3>
  
  
  範例 3：使用 do-while 循環
</h3>

<p>do-while 迴圈對於陣列遍歷較不常見，但在某些情況下很有用。 <br>
</p>

<pre class="brush:php;toolbar:false">function printReverseUntilZero(arr) {
    let i = arr.length - 1;
    do {
        console.log(arr[i]);
        i--;
    } while (i >= 0 && arr[i] !== 0);
}

const numbers = [1, 3, 0, 5, 7];
printReverseUntilZero(numbers); // Output: 7, 5

時間複雜度：最壞情況下為 O(n)，但如果儘早遇到零，時間複雜度可能會更低。

範例4：反向遍歷

逆序遍歷數組是許多演算法中的常見操作。

function reverseTraversal(arr) {
    const result = [];
    for (let i = arr.length - 1; i >= 0; i--) {
        result.push(arr[i]);
    }
    return result;
}

const numbers = [1, 2, 3, 4, 5];
console.log(reverseTraversal(numbers)); // Output: [5, 4, 3, 2, 1]

時間複雜度：O(n)，其中n是陣列的長度。

3. 現代 JavaScript 陣列方法

ES6 和更高版本的 JavaScript 引入了強大的陣列方法，可以簡化遍歷和操作。

範例 5：forEach 方法

forEach 方法提供了一種迭代數組元素的簡潔方法。

function logEvenNumbers(arr) {
    arr.forEach(num => {
        if (num % 2 === 0) {
            console.log(num);
        }
    });
}

const numbers = [1, 2, 3, 4, 5, 6];
logEvenNumbers(numbers); // Output: 2, 4, 6

時間複雜度：O(n)，其中n是陣列的長度。

範例6：map方法

map 方法建立一個新數組，其中包含對每個元素呼叫提供的函數的結果。

function doubleNumbers(arr) {
    return arr.map(num => num * 2);
}

const numbers = [1, 2, 3, 4, 5];
console.log(doubleNumbers(numbers)); // Output: [2, 4, 6, 8, 10]

時間複雜度：O(n)，其中n是陣列的長度。

實施例7：過濾法

filter 方法建立一個新數組，其中包含滿足特定條件的所有元素。

function filterPrimes(arr) {
    function isPrime(num) {
        if (num 



<p><strong>時間複雜度</strong>：O(n * sqrt(m))，其中n是陣列的長度，m是陣列中最大的數字。 </p>

<p></p>

<h3>
  
  
  範例8：reduce方法
</h3>

<p>reduce 方法將縮減函數應用於陣列的每個元素，從而產生單一輸出值。 <br>
</p>

<pre class="brush:php;toolbar:false">function findMax(arr) {
    return arr.reduce((max, current) => Math.max(max, current), arr[0]);
}

const numbers = [3, 7, 2, 9, 1, 5];
console.log(findMax(numbers)); // Output: 9

時間複雜度：O(n)，其中n是陣列的長度。

4. 中級遍歷技術

現在讓我們來探索一些陣列遍歷的中間技巧。

例9：兩指針技術

兩指針技術通常用於高效解決數組相關問題。

function isPalindrome(arr) {
    let left = 0;
    let right = arr.length - 1;
    while (left 



<p><strong>Time Complexity</strong>: O(n/2) which simplifies to O(n), where n is the length of the array.</p>

<p></p>

<h3>
  
  
  Example 10: Sliding window
</h3>

<p>The sliding window technique is useful for solving problems involving subarrays or subsequences.<br>
</p>

<pre class="brush:php;toolbar:false">function maxSubarraySum(arr, k) {
    if (k > arr.length) return null;

    let maxSum = 0;
    let windowSum = 0;

    // Calculate sum of first window
    for (let i = 0; i 



<p><strong>Time Complexity</strong>: O(n), where n is the length of the array.</p>

<p></p>

<h3>
  
  
  Example 11: Kadane's Algorithm
</h3>

<p>Kadane's algorithm is used to find the maximum subarray sum in a one-dimensional array.<br>
</p>

<pre class="brush:php;toolbar:false">function maxSubarraySum(arr) {
    let maxSoFar = arr[0];
    let maxEndingHere = arr[0];

    for (let i = 1; i 



<p><strong>Time Complexity</strong>: O(n), where n is the length of the array.</p>

<p></p>

<h3>
  
  
  Example 12: Dutch National Flag Algorithm
</h3>

<p>This algorithm is used to sort an array containing three distinct elements.<br>
</p>

<pre class="brush:php;toolbar:false">function dutchFlagSort(arr) {
    let low = 0, mid = 0, high = arr.length - 1;

    while (mid 



<p><strong>Time Complexity</strong>: O(n), where n is the length of the array.</p>

<p></p>

<h2>
  
  
  5. Advanced Traversal Techniques
</h2>

<p>Let's explore some more advanced techniques for array traversal.</p>

<p></p>

<h3>
  
  
  Example 13: Recursive traversal
</h3>

<p>Recursive traversal can be powerful for certain types of problems, especially those involving nested structures.<br>
</p>

<pre class="brush:php;toolbar:false">function sumNestedArray(arr) {
    let sum = 0;
    for (let element of arr) {
        if (Array.isArray(element)) {
            sum += sumNestedArray(element);
        } else {
            sum += element;
        }
    }
    return sum;
}

const nestedNumbers = [1, [2, 3], [[4, 5], 6]];
console.log(sumNestedArray(nestedNumbers)); // Output: 21

Time Complexity: O(n), where n is the total number of elements including nested ones.

Example 14: Binary search on sorted array

Binary search is an efficient algorithm for searching a sorted array.

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left 



<p><strong>Time Complexity</strong>: O(log n), where n is the length of the array.</p>

<p></p>

<h3>
  
  
  Example 15: Merge two sorted arrays
</h3>

<p>This technique is often used in merge sort and other algorithms.<br>
</p>

<pre class="brush:php;toolbar:false">function mergeSortedArrays(arr1, arr2) {
    const mergedArray = [];
    let i = 0, j = 0;

    while (i 



<p><strong>Time Complexity</strong>: O(n + m), where n and m are the lengths of the input arrays.</p>

<p></p>

<h3>
  
  
  Example 16: Quick Select Algorithm
</h3>

<p>Quick Select is used to find the kth smallest element in an unsorted array.<br>
</p>

<pre class="brush:php;toolbar:false">function quickSelect(arr, k) {
    if (k  arr.length) {
        return null;
    }

    function partition(low, high) {
        const pivot = arr[high];
        let i = low - 1;

        for (let j = low; j  k - 1) {
            return select(low, pivotIndex - 1, k);
        } else {
            return select(pivotIndex + 1, high, k);
        }
    }

    return select(0, arr.length - 1, k);
}

const numbers = [3, 2, 1, 5, 6, 4];
console.log(quickSelect(numbers, 2)); // Output: 2 (2nd smallest element)

Time Complexity: Average case O(n), worst case O(n^2), where n is the length of the array.

6. Specialized Traversals

Some scenarios require specialized traversal techniques, especially when dealing with multi-dimensional arrays.

Example 17: Traversing a 2D array

Traversing 2D arrays (matrices) is a common operation in many algorithms.

function traverse2DArray(matrix) {
    const result = [];
    for (let i = 0; i 



<p><strong>Time Complexity</strong>: O(m * n), where m is the number of rows and n is the number of columns in the matrix.</p>

<p></p>

<h3>
  
  
  Example 18: Spiral Matrix Traversal
</h3>

<p>Spiral traversal is a more complex pattern often used in coding interviews and specific algorithms.<br>
</p>

<pre class="brush:php;toolbar:false">function spiralTraversal(matrix) {
    const result = [];
    if (matrix.length === 0) return result;

    let top = 0, bottom = matrix.length - 1;
    let left = 0, right = matrix[0].length - 1;

    while (top = left; i--) {
                result.push(matrix[bottom][i]);
            }
            bottom--;
        }

        if (left = top; i--) {
                result.push(matrix[i][left]);
            }
            left++;
        }
    }

    return result;
}

const matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9, 10, 11, 12]
];
console.log(spiralTraversal(matrix));
// Output: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix.

Example 19: Diagonal Traversal

Diagonal traversal of a matrix is another interesting pattern.

function diagonalTraversal(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const result = [];

    for (let d = 0; d = 0 && j 



<p><strong>Time Complexity</strong>: O(m * n), where m is the number of rows and n is the number of columns in the matrix.</p>

<p></p>

<h3>
  
  
  Example 20: Zigzag Traversal
</h3>

<p>Zigzag traversal is a pattern where we traverse the array in a zigzag manner.<br>
</p>

<pre class="brush:php;toolbar:false">function zigzagTraversal(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const result = [];
    let row = 0, col = 0;
    let goingDown = true;

    for (let i = 0; i 



<p><strong>Time Complexity</strong>: O(m * n), where m is the number of rows and n is the number of columns in the matrix.</p>

<p></p>

<h2>
  
  
  7. Performance Considerations
</h2>

<p>When working with array traversals, it's important to consider performance implications:</p>

<ol>
<li><p><strong>Time Complexity</strong>: Most basic traversals have O(n) time complexity, where n is the number of elements. However, nested loops or recursive calls can increase this to O(n^2) or higher.</p></li>
<li><p><strong>Space Complexity</strong>: Methods like map and filter create new arrays, potentially doubling memory usage. In-place algorithms are more memory-efficient.</p></li>
<li><p><strong>Iterator Methods vs. For Loops</strong>: Modern methods like forEach, map, and filter are generally slower than traditional for loops but offer cleaner, more readable code.</p></li>
<li><p><strong>Early Termination</strong>: for and while loops allow for early termination, which can be more efficient when you're searching for a specific element.</p></li>
<li><p><strong>Large Arrays</strong>: For very large arrays, consider using for loops for better performance, especially if you need to break the loop early.</p></li>
<li><p><strong>Caching Array Length</strong>: In performance-critical situations, caching the array length in a variable before the loop can provide a slight speed improvement.</p></li>
<li><p><strong>Avoiding Array Resizing</strong>: When building an array dynamically, initializing it with a predetermined size (if possible) can improve performance by avoiding multiple array resizing operations.</p></li>
</ol>

<p></p><h2>
  
  
  8.LeetCode練習題
</h2>

<p>為了進一步加深您對陣列遍歷技術的理解，您可以練習以下 15 個 LeetCode 問題：</p>

<ol>
<li>兩和</li>
<li>買賣股票的最佳時機</li>
<li>包含重複</li>
<li>除自身之外的陣列的乘積</li>
<li>最大子數組</li>
<li>移動零</li>
<li>3Sum</li>
<li>裝最多水的容器</li>
<li>旋轉數組</li>
<li>找出旋轉排序數組中的最小值</li>
<li>在旋轉排序數組中搜尋</li>
<li>合併間隔</li>
<li>螺旋矩陣</li>
<li>設定矩陣零</li>
<li>最長連續序列</li>
</ol>

<p>這些問題涵蓋了廣泛的陣列遍歷技術，並將幫助您應用我們在本部落格文章中討論的概念。 </p>

<p></p>

<h2>
  
  
  9. 結論
</h2>

<p>陣列遍歷是程式設計中的基本技能，它構成了許多演算法和資料操作的基礎。從基本的 for 迴圈到滑動視窗和專門的矩陣遍歷等高級技術，掌握這些方法將顯著增強您高效解決複雜問題的能力。 </p>

<p>正如您透過這 20 個範例所看到的，JavaScript 提供了一組豐富的陣列遍歷工具，每個工具都有自己的優勢和用例。透過了解何時以及如何應用每種技術，您將有能力應對各種程式設計挑戰。 </p>

<p>記住，熟練的關鍵是練習。嘗試在您自己的專案中實現這些遍歷方法，當您對基礎知識越來越熟悉時，請毫不猶豫地探索更高級的技術。提供的 LeetCode 問題將為您提供充足的機會在各種場景中應用這些概念。 </p>

<p>當您繼續發展自己的技能時，請務必牢記您選擇的遍歷方法對效能的影響。有時，簡單的 for 迴圈可能是最有效的解決方案，而在其他情況下，更專業的技術（如滑動視窗或兩個指標方法）可能是最佳的。 </p>

<p>祝您編碼愉快，願您的陣列始終能夠有效率地遍歷！ </p>


          

            
        

以上是使用 JavaScript 在 DSA 中進行陣列遍歷：從基礎知識到進階技術的詳細內容。更多資訊請關注PHP中文網其他相關文章！