使用 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 < arr.length; i++) {
        sum += arr[i];
    }
    return sum;
}

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

时间复杂度：O(n)，其中n是数组的长度。

示例 2：使用 while 循环

while循环也可以用于数组遍历，特别是当终止条件比较复杂时。

function findFirstNegative(arr) {
    let i = 0;
    while (i < arr.length && arr[i] >= 0) {
        i++;
    }
    return i < arr.length ? arr[i] : "No negative number found";
}

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

时间复杂度：最坏情况下为 O(n)，但如果尽早发现负数，时间复杂度可能会更低。

示例 3：使用 do-while 循环

do-while 循环对于数组遍历不太常见，但在某些情况下很有用。

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 <= 1) return false;
        for (let i = 2; i <= Math.sqrt(num); i++) {
            if (num % i === 0) return false;
        }
        return true;
    }

    return arr.filter(isPrime);
}

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

时间复杂度：O(n * sqrt(m))，其中n是数组的长度，m是数组中最大的数字。

示例8：reduce方法

reduce 方法将缩减函数应用于数组的每个元素，从而产生单个输出值。

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 < right) {
        if (arr[left] !== arr[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

console.log(isPalindrome([1, 2, 3, 2, 1])); // Output: true
console.log(isPalindrome([1, 2, 3, 4, 5])); // Output: false

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

Example 10: Sliding window

The sliding window technique is useful for solving problems involving subarrays or subsequences.

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 < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;

    // Slide the window
    for (let i = k; i < arr.length; i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

const numbers = [1, 4, 2, 10, 23, 3, 1, 0, 20];
console.log(maxSubarraySum(numbers, 4)); // Output: 39

Time Complexity: O(n), where n is the length of the array.

Example 11: Kadane's Algorithm

Kadane's algorithm is used to find the maximum subarray sum in a one-dimensional array.

function maxSubarraySum(arr) {
    let maxSoFar = arr[0];
    let maxEndingHere = arr[0];

    for (let i = 1; i < arr.length; i++) {
        maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }

    return maxSoFar;
}

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

Time Complexity: O(n), where n is the length of the array.

Example 12: Dutch National Flag Algorithm

This algorithm is used to sort an array containing three distinct elements.

function dutchFlagSort(arr) {
    let low = 0, mid = 0, high = arr.length - 1;

    while (mid <= high) {
        if (arr[mid] === 0) {
            [arr[low], arr[mid]] = [arr[mid], arr[low]];
            low++;
            mid++;
        } else if (arr[mid] === 1) {
            mid++;
        } else {
            [arr[mid], arr[high]] = [arr[high], arr[mid]];
            high--;
        }
    }

    return arr;
}

const numbers = [2, 0, 1, 2, 1, 0];
console.log(dutchFlagSort(numbers)); // Output: [0, 0, 1, 1, 2, 2]

Time Complexity: O(n), where n is the length of the array.

5. Advanced Traversal Techniques

Let's explore some more advanced techniques for array traversal.

Example 13: Recursive traversal

Recursive traversal can be powerful for certain types of problems, especially those involving nested structures.

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 <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1; // Target not found
}

const sortedNumbers = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(sortedNumbers, 7)); // Output: 3
console.log(binarySearch(sortedNumbers, 6)); // Output: -1

Time Complexity: O(log n), where n is the length of the array.

Example 15: Merge two sorted arrays

This technique is often used in merge sort and other algorithms.

function mergeSortedArrays(arr1, arr2) {
    const mergedArray = [];
    let i = 0, j = 0;

    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] <= arr2[j]) {
            mergedArray.push(arr1[i]);
            i++;
        } else {
            mergedArray.push(arr2[j]);
            j++;
        }
    }

    while (i < arr1.length) {
        mergedArray.push(arr1[i]);
        i++;
    }

    while (j < arr2.length) {
        mergedArray.push(arr2[j]);
        j++;
    }

    return mergedArray;
}

const arr1 = [1, 3, 5, 7];
const arr2 = [2, 4, 6, 8];
console.log(mergeSortedArrays(arr1, arr2)); // Output: [1, 2, 3, 4, 5, 6, 7, 8]

Time Complexity: O(n + m), where n and m are the lengths of the input arrays.

Example 16: Quick Select Algorithm

Quick Select is used to find the kth smallest element in an unsorted array.

function quickSelect(arr, k) {
    if (k < 1 || k > arr.length) {
        return null;
    }

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

        for (let j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                [arr[i], arr[j]] = [arr[j], arr[i]];
            }
        }

        [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
        return i + 1;
    }

    function select(low, high, k) {
        const pivotIndex = partition(low, high);

        if (pivotIndex === k - 1) {
            return arr[pivotIndex];
        } else if (pivotIndex > 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 < matrix.length; i++) {
        for (let j = 0; j < matrix[i].length; j++) {
            result.push(matrix[i][j]);
        }
    }
    return result;
}

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

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

Example 18: Spiral Matrix Traversal

Spiral traversal is a more complex pattern often used in coding interviews and specific algorithms.

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 <= bottom && left <= right) {
        // Traverse right
        for (let i = left; i <= right; i++) {
            result.push(matrix[top][i]);
        }
        top++;

        // Traverse down
        for (let i = top; i <= bottom; i++) {
            result.push(matrix[i][right]);
        }
        right--;

        if (top <= bottom) {
            // Traverse left
            for (let i = right; i >= left; i--) {
                result.push(matrix[bottom][i]);
            }
            bottom--;
        }

        if (left <= right) {
            // Traverse up
            for (let i = bottom; i >= 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 < m + n - 1; d++) {
        const temp = [];
        for (let i = 0; i < m; i++) {
            const j = d - i;
            if (j >= 0 && j < n) {
                temp.push(matrix[i][j]);
            }
        }
        if (d % 2 === 0) {
            result.push(...temp.reverse());
        } else {
            result.push(...temp);
        }
    }

    return result;
}

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

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

Example 20: Zigzag Traversal

Zigzag traversal is a pattern where we traverse the array in a zigzag manner.

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 < m * n; i++) {
        result.push(matrix[row][col]);

        if (goingDown) {
            if (row === m - 1 || col === 0) {
                goingDown = false;
                if (row === m - 1) {
                    col++;
                } else {
                    row++;
                }
            } else {
                row++;
                col--;
            }
        } else {
            if (col === n - 1 || row === 0) {
                goingDown = true;
                if (col === n - 1) {
                    row++;
                } else {
                    col++;
                }
            } else {
                row--;
                col++;
            }
        }
    }

    return result;
}

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

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

7. Performance Considerations

When working with array traversals, it's important to consider performance implications:

1. Time Complexity: 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.

2. Space Complexity: Methods like map and filter create new arrays, potentially doubling memory usage. In-place algorithms are more memory-efficient.

3. Iterator Methods vs. For Loops: Modern methods like forEach, map, and filter are generally slower than traditional for loops but offer cleaner, more readable code.

4. Early Termination: for and while loops allow for early termination, which can be more efficient when you're searching for a specific element.

5. Large Arrays: For very large arrays, consider using for loops for better performance, especially if you need to break the loop early.

6. Caching Array Length: In performance-critical situations, caching the array length in a variable before the loop can provide a slight speed improvement.

7. Avoiding Array Resizing: When building an array dynamically, initializing it with a predetermined size (if possible) can improve performance by avoiding multiple array resizing operations.

8.LeetCode练习题

为了进一步加深您对数组遍历技术的理解，您可以练习以下 15 个 LeetCode 问题：

1. 两和
2. 买卖股票的最佳时机
3. 包含重复
4. 除自身之外的数组的乘积
5. 最大子数组
6. 移动零
7. 3Sum
8. 装最多水的容器
9. 旋转数组
10. 查找旋转排序数组中的最小值
11. 在旋转排序数组中搜索
12. 合并间隔
13. 螺旋矩阵
14. 设置矩阵零
15. 最长连续序列

这些问题涵盖了广泛的数组遍历技术，并将帮助您应用我们在本博文中讨论的概念。

9. 结论

数组遍历是编程中的一项基本技能，它构成了许多算法和数据操作的基础。从基本的 for 循环到滑动窗口和专门的矩阵遍历等高级技术，掌握这些方法将显着增强您高效解决复杂问题的能力。

正如您通过这 20 个示例所看到的，JavaScript 提供了一组丰富的数组遍历工具，每个工具都有自己的优势和用例。通过了解何时以及如何应用每种技术，您将有能力应对各种编程挑战。

记住，熟练的关键是练习。尝试在您自己的项目中实现这些遍历方法，当您对基础知识越来越熟悉时，请毫不犹豫地探索更高级的技术。提供的 LeetCode 问题将为您提供充足的机会在各种场景中应用这些概念。

当您继续发展自己的技能时，请始终牢记您选择的遍历方法对性能的影响。有时，简单的 for 循环可能是最有效的解决方案，而在其他情况下，更专业的技术（例如滑动窗口或两指针方法）可能是最佳的。

祝您编码愉快，愿您的数组始终能够高效地遍历！

以上是使用 JavaScript 在 DSA 中进行数组遍历：从基础知识到高级技术的详细内容。更多信息请关注PHP中文网其他相关文章！