本文共 1924 字，大约阅读时间需要 6 分钟。

基础数据结构及其应用

数组与链表

在实际开发中，数据结构的选择对性能优化至关重要。以下是常见的两种数据结构及其应用场景的分析。

1.1 数组

数组是一种Linear+Direct的数据结构，具有随机访问性质的优势。在运行时内存中连续存储，支持固定大小，适用于数据量较小且访问模式明确的场景。以下是常见应用：

1.1.1 前缀和

适用场景：原始数组不发生修改，需频繁计算某区间的累加和。

function prefixSum(nums) {
    const preSum = new Array(nums.length + 1).fill(0);
    for (let i = 1; i <= nums.length; i++) {
        preSum[i] = preSum[i - 1] + nums[i - 1];
    }
    return preSum;
}
function query(preSum, i, j) {
    return preSum[j + 1] - preSum[i];
}

特点：支持O(1)时间复杂度的区间和查询，适合数据获取率要求高的场景。

1.1.2 差分数组

适用场景：对原始数组的某个区间进行增减操作，需要频繁维护数据结构。

function difference(nums) {
    const diff = new Array(nums.length + 1).fill(0);
    diff[0] = nums[0];
    for (let i = 1; i <= nums.length; i++) {
        diff[i] = nums[i] - nums[i - 1];
    }
    return diff;
}
function increment(i, j, inc) {
    diff[i] += inc;
    diff[j + 1] -= inc;
}
function result(length, diff) {
    const res = new Array(length).fill(0);
    res[0] = diff[0];
    for (let i = 1; i < res.length; i++) {
        res[i] = res[i - 1] + diff[i];
    }
    return res;
}

特点：支持O(1)时间复杂度的增减操作，适合动态修改数据的场景。

1.1.3 快慢指针

快慢指针技术常用于链表中实现复杂操作，下面是其典型应用场景：

快慢指针相遇时，若存在环则返回true，否则返回false。

const hasCycle = function(head) {
    let slow = fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    return false;
};

2. 查找环的起始位置

假设已知存在环，重复操作至相遇点，再将慢指针从相遇点移动至环起点即可。

3. 寻找链表的倒数第n个元素

让快指针提前n步，然后同时移动快慢指针，最终慢指针所在位置即为目标。

const removeNthFromEnd = function(head, n) {
    let slow = fast = head;
    for (let i = 0; i < n; i++) {
        fast = fast.next;
    }
    if (fast === null) return head;
    while (fast && fast.next) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return head;
};

1.1.4 左右指针

左右指针技术在链表的某些特定操作中也具有重要作用，具体场景需根据实际需求确定。

---

总结

对数据结构的理解与应用是编程中的核心能力，掌握了前缀和、差分数组、快慢指针等技术，在解决实际问题中能事半功倍。每种技术的选择都应基于具体需求，确保最优的性能与效率。