2025-06-17

algorithms►leetcode

023-两数相加（虚拟头节点）

问题重述

给定两个非空的链表，表示两个非负整数。链表中每个节点存储一个数字，且数字是逆序存储的（即链表的第一个节点是个位数，第二个节点是十位数，依此类推）。要求将这两个数相加，并返回一个同样以逆序方式存储的和的链表。

示例

输入：

l1 = [2, 4, 3] （表示 342）
l2 = [5, 6, 4] （表示 465）

输出：

[7, 0, 8] （因为 342 + 465 = 807，逆序存储为 7 -> 0 -> 8）

解决思路

初始化：
- 创建一个虚拟头节点（dummy），简化链表操作。
- 初始化 current 指针指向 dummy。
- 初始化进位 carry 为 0。
遍历链表：
- 同时遍历 l1 和 l2，直到两个链表都遍历完且进位 carry 为 0。
- 每次取出当前节点的值（如果链表已遍历完，则取 0）。
- 计算 sum = val1 + val2 + carry。
- 更新 carry = Math.floor(sum / 10)。
- 创建新节点，值为 sum % 10，并链接到 current.next。
- 移动 current 到新节点。
- 移动 l1 和 l2（如果存在）。
处理剩余的进位：
- 如果遍历完链表后 carry > 0，则额外添加一个节点。
返回结果：
- dummy.next 就是新链表的头节点。

JavaScript 实现

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}

function addTwoNumbers(l1, l2) {
    let dummy = new ListNode(0); // 虚拟头节点
    let current = dummy;
    let carry = 0;

    while (l1 || l2 || carry) {
        const val1 = l1 ? l1.val : 0;
        const val2 = l2 ? l2.val : 0;

        const sum = val1 + val2 + carry;
        carry = Math.floor(sum / 10); // 计算进位
        current.next = new ListNode(sum % 10); // 新节点
        current = current.next; // 移动指针

        if (l1) l1 = l1.next;
        if (l2) l2 = l2.next;
    }

    return dummy.next; // 返回真正的头节点
}

测试示例

// 示例测试
const l1 = new ListNode(2, new ListNode(4, new ListNode(3))); // 2 -> 4 -> 3 (342)
const l2 = new ListNode(5, new ListNode(6, new ListNode(4))); // 5 -> 6 -> 4 (465)

const result = addTwoNumbers(l1, l2); // 7 -> 0 -> 8 (807)

// 打印结果
let output = [];
let node = result;
while (node) {
    output.push(node.val);
    node = node.next;
}
console.log(output); // [7, 0, 8]

复杂度分析

时间复杂度：O(max(n, m))，其中 n 和 m 分别是 l1 和 l2 的长度。
空间复杂度：O(max(n, m))，新链表的长度最多为 max(n, m) + 1（如果最后有进位）。

总结

使用虚拟头节点简化链表操作。
逐位相加，并处理进位。
**遍历直到两个链表都结束且进位为 0**。
返回 dummy.next 作为结果链表的头节点。

2025-06-17

algorithms►leetcode

024-和为K的子数组（前缀和）

560. 和为 K 的子数组-Medium

提示

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k* **的子数组的个数 *。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

一步步详细解答：前缀和 + 哈希表方法

1. 问题理解

我们需要统计数组中连续子数组的和等于 k 的个数。例如：

nums = [1,1,1], k = 2 → 输出 2（因为 [1,1] 和 [1,1] 都满足）
nums = [1,2,3], k = 3 → 输出 2（因为 [1,2] 和 [3] 都满足）

2. 暴力解法（O(n²)）

最直观的方法是双重循环，计算所有可能的子数组的和：

var subarraySum = function(nums, k) {
    let count = 0;
    for (let start = 0; start < nums.length; start++) {
        let sum = 0;
        for (let end = start; end < nums.length; end++) {
            sum += nums[end]; // 计算从 start 到 end 的和
            if (sum === k) {
                count++;
            }
        }
    }
    return count;
};

缺点：当 nums 很大时，效率很低（比如 nums.length = 10^5 时，计算量会非常大）。

3. 优化解法：前缀和 + 哈希表（O(n)）

为了优化，我们引入**前缀和（Prefix Sum）**的概念。

什么是前缀和？

前缀和是指从数组开头到当前位置的所有元素的和。例如：

nums = [1, 2, 3] 的前缀和数组是 [0, 1, 3, 6]（初始 0 是为了方便计算）。

为什么用前缀和？

假设我们有一个子数组 nums[i..j]，它的和可以表示为：

sum(nums[i..j]) = prefixSum[j+1] - prefixSum[i]

如果我们希望 sum(nums[i..j]) = k，那么：

prefixSum[j+1] - prefixSum[i] = k
=> prefixSum[j+1] - k = prefixSum[i]

也就是说，**如果 prefixSum[j+1] - k 在之前的前缀和中出现过，就说明存在一个子数组的和等于 k**。

如何用哈希表优化？

我们可以用一个哈希表 map 存储前缀和出现的次数，这样可以在 O(1) 时间内查询 prefixSum[j+1] - k 是否出现过。

代码实现

var subarraySum = function(nums, k) {
    let count = 0;
    let sum = 0;
    const map = new Map();
    map.set(0, 1); // 初始状态，前缀和为 0 出现 1 次

    for (let i = 0; i < nums.length; i++) {
        sum += nums[i]; // 计算当前的前缀和
        if (map.has(sum - k)) { // 检查 sum - k 是否出现过
            count += map.get(sum - k); // 如果有，说明存在子数组和为 k
        }
        map.set(sum, (map.get(sum) || 0) + 1); // 更新当前前缀和的出现次数
    }
    return count;
};

示例解析

例子 1：nums = [1,1,1], k = 2

i	nums[i]	sum (prefixSum)	sum - k	map (sum → count)	count
-	-	0	-	{0:1}	0
0	1	1	1-2=-1	{0:1, 1:1}	0
1	1	2	2-2=0	{0:1, 1:1, 2:1}	1
2	1	3	3-2=1	{0:1, 1:1, 2:1, 3:1}	2

**最终 count = 2**，符合预期。

例子 2：nums = [1,2,3], k = 3

i	nums[i]	sum (prefixSum)	sum - k	map (sum → count)	count
-	-	0	-	{0:1}	0
0	1	1	1-3=-2	{0:1, 1:1}	0
1	2	3	3-3=0	{0:1, 1:1, 3:1}	1
2	3	6	6-3=3	{0:1, 1:1, 3:1, 6:1}	2