01. 双指针-只有一个输入, 从两端开始遍历

August 11, 2023 0 - 算法, 0.0 - 算法模版

正文

双指针（Two Pointers）是一种常用于数组或字符串问题的技巧。当我们需要在有序序列中查找符合特定条件的元素对，或者判断序列是否具有某种属性（如回文）时，从两端向中间遍历是非常高效的。

算法模板

fun doublePointer(arr: IntArray): Int {
    var left = 0
    var right = arr.size - 1

    while (left < right) {
        // 根据 left 和 right 相关的条件进行操作
        // 例如：if (arr[left] + arr[right] == target) return ...
        
        if (CONDITION) {
            left++
        } else {
            right--
        }
    }

    return 0 // 返回需要的结果
}

使用说明

适用场景：
- 有序数组：如两数之和（有序版）、三数之和。
- 字符串处理：如判断回文字符串、反转数组/字符串。
- 容器盛水问题：如“盛最多水的容器”。
核心优势：
- 能够将 $O(N^2)$ 的暴力枚举优化到 $O(N)$。
- 利用了序列的有序性或特定单调性。
注意点：
- 循环条件通常是 left < right（找对子）或 left <= right（处理中间元素）。
- 更新指针时要确保逻辑能够覆盖所有情况，避免死循环。

02. 双指针-有两个输入, 两个都需要遍历完

August 11, 2023 0 - 算法, 0.0 - 算法模版

正文

fun twoPointers(nums1: IntArray, nums2: IntArray) {
    var pointer1 = 0
    var pointer2 = 0

    while (pointer1 < nums1.size && pointer2 < nums2.size) {
        // 处理指针1和指针2对应位置的元素
        // ...

        // 移动指针
        pointer1++
        pointer2++
    }

    // 处理剩余未遍历完的元素
    while (pointer1 < nums1.size) {
        // 处理指针1对应位置的元素
        // ...
        pointer1++
    }

    while (pointer2 < nums2.size) {
        // 处理指针2对应位置的元素
        // ...
        pointer2++
    }
}

03. 滑动窗口

August 11, 2023 0 - 算法, 0.0 - 算法模版

正文

滑动窗口（Sliding Window）是一种在数组或字符串上执行操作的优化技术。它将嵌套循环的问题转化为单个循环，从而显著降低时间复杂度。

算法模板（固定窗口大小）

fun slidingWindow(nums: IntArray, k: Int): Int {
    val n = nums.size
    if (n < k) return 0
    
    var sum = 0
    var maxSum = 0

    // 1. 初始化：计算第一个窗口的和
    for (i in 0 until k) {
        sum += nums[i]
    }

    maxSum = sum

    // 2. 滑动：从第 k 个元素开始遍历
    for (i in k until n) {
        // 新窗口的和 = 前一个窗口的和 + 新进入的元素 - 离开窗口的元素
        sum += nums[i] - nums[i - k]
        // 更新结果
        maxSum = maxOf(maxSum, sum)
    }

    return maxSum
}

使用说明

适用场景：
- 固定窗口：给定窗口大小 $k$，求最大/最小和、平均值等。
- 可变窗口：寻找满足特定条件的最长/最短子数组（通常配合双指针 left, right 使用）。
核心优势：
- 避免了重复计算窗口重叠部分的值。
- 时间复杂度通常为 $O(N)$。
注意点：
- 注意边界条件，如数组长度小于 $k$ 的情况。
- 如果是求平均值，注意浮点数转换。
- 对于可变窗口，通常逻辑是：右边界右移增加元素 -> 窗口不满足条件时左边界右移移除元素。

04. 构建前缀和

August 11, 2023 0 - 算法, 0.0 - 算法模版

正文

前缀和（Prefix Sum）是一种非常重要的预处理技巧，主要用于高效计算数组中任意区间的元素之和。

算法模板

fun prefixSum(nums: IntArray): IntArray {
    // 前缀和数组长度为 n + 1，prefixSum[i] 表示 nums 中前 i 个元素的和
    val prefixSum = IntArray(nums.size + 1)

    // 计算前缀和数组
    for (i in 1..nums.size) {
        prefixSum[i] = prefixSum[i - 1] + nums[i - 1]
    }
    
    return prefixSum
}

使用说明

区间求和：
使用前缀和数组 prefixSum，我们可以以 $O(1)$ 的时间复杂度回答多个区间和查询。计算区间 [left, right]（包含两端）的元素之和：
1
val sum = prefixSum[right + 1] - prefixSum[left]
核心优势：
将多次区间查询的时间复杂度从 $O(N)$ 降低到 $O(1)$。
注意点：
- 前缀和数组长度通常设为 n + 1，其中 prefixSum[0] = 0。这样可以统一处理 left = 0 的边界情况，无需额外的 if 判断。
- 如果数组元素较大，注意前缀和数组可能发生整型溢出，必要时使用 LongArray。

05. 高效的字符串构建

August 11, 2023 0 - 算法, 0.0 - 算法模版

正文

以下是一个高效的字符串构建算法模板：

fun buildString(chars: List<Char>): String {
    val sb = StringBuilder()

    for (ch in chars) {
        sb.append(ch)
    }
    
    return sb.toString()
}

在这个模板中，我们使用 StringBuilder 来构建字符串。StringBuilder 是可变的字符串类，可以高效地进行字符串的拼接操作。

我们通过遍历字符列表 chars，逐个将字符添加到 StringBuilder 中。最后，通过调用 toString() 方法，将 StringBuilder 转换为最终的字符串结果并返回。

使用 StringBuilder 的好处是它避免了在每次拼接字符串时创建新的字符串对象，从而提高了性能和效率。特别是在需要频繁拼接大量字符串的情况下，使用 StringBuilder 可以避免不必要的性能损耗。

使用这个模板，你可以根据具体需求构建字符串。可以根据问题的要求在遍历过程中进行一些字符处理、条件判断等操作。

06. 链表-快慢指针

August 11, 2023 0 - 算法, 0.0 - 算法模版

正文

在模板中，我们使用两个指针，一个指针每次向后移动一个节点，另一个指针每次向后移动两个节点。如果链表中存在循环，快指针最终会追上慢指针，这样我们就可以判断出链表有循环。如果链表没有循环，快指针会先到达链表的末尾，此时我们就可以判断链表没有循环。

fun hasCycle(head: ListNode?): Boolean {
    var slow = head
    var fast = head

    while (fast?.next != null && fast.next?.next != null) {
        slow = slow?.next
        fast = fast.next?.next

        if (slow == fast) {
            return true
        }
    }

    return false
}

07. 反转链表

August 11, 2023 0 - 算法, 0.0 - 算法模版

正文

反转链表（Reverse Linked List）是链表操作中最基础且最高频的考点。它通过改变节点间的指针指向，将原本 A -> B -> C 的结构变为 C -> B -> A。

算法模板

class ListNode(var value: Int) {
    var next: ListNode? = null
}

fun reverseList(head: ListNode?): ListNode? {
    var prev: ListNode? = null
    var current = head
    
    while (current != null) {
        val nextNode = current.next // 1. 暂存下一个节点
        current.next = prev         // 2. 反转当前节点的指向
        prev = current              // 3. prev 向前移动
        current = nextNode          // 4. current 向前移动
    }

    return prev // 新的头节点
}

使用说明

核心逻辑：
在遍历过程中，我们需要维持三个变量：prev（已反转部分的头）、current（当前处理的节点）和 nextNode（待处理部分的头）。
关键步骤：
反转指针前，**必须先暂存 current.next**，否则一旦修改了 current.next，就无法找到链表的后续部分。
时间与空间复杂度：
- 时间复杂度：$O(N)$，只需遍历一次链表。
- 空间复杂度：$O(1)$，仅需常数级别的额外空间。
注意点：
- 空链表或只有一个节点的链表应能正常工作。
- 在 Kotlin 中，注意处理可空性（ListNode?）。

08. 找到符合确切条件的子数组数

August 11, 2023 0 - 算法, 0.0 - 算法模版

正文

在算法面试中，“找到符合确切条件的子数组数”通常有两种核心解法：前缀和 + 哈希表（通用性最强）或 双指针/滑动窗口（适用于非负数序列）。

方案一：前缀和 + 哈希表 (通用模板)

这是解决该类问题的“银弹”，适用于数组中包含负数的情况。

fun numSubarraysWithSum(nums: IntArray, goal: Int): Int {
    var count = 0
    var prefixSum = 0
    // key: 前缀和的值, value: 该前缀和出现的次数
    val map = mutableMapOf<Int, Int>()
    // 初始化：前缀和为 0 已经出现过 1 次
    map[0] = 1

    for (num in nums) {
        prefixSum += num
        // 如果 prefixSum - goal 存在于 map 中，说明存在子数组和为 goal
        count += map.getOrDefault(prefixSum - goal, 0)
        // 更新当前前缀和的出现次数
        map[prefixSum] = map.getOrDefault(prefixSum, 0) + 1
    }

    return count
}

方案二：双指针 / 滑动窗口 (针对非负数优化)

如果数组中元素全部非负，使用滑动窗口可以将空间复杂度降低到 $O(1)$。

// 统计和正好为 goal 的子数组数量
fun numSubarraysWithSumSlidingWindow(nums: IntArray, goal: Int): Int {
    // 技巧：正好为 K = 最多为 K - 最多为 K-1
    return atMost(nums, goal) - atMost(nums, goal - 1)
}

private fun atMost(nums: IntArray, goal: Int): Int {
    if (goal < 0) return 0
    var left = 0
    var sum = 0
    var count = 0
    for (right in nums.indices) {
        sum += nums[right]
        while (sum > goal) {
            sum -= nums[left]
            left++
        }
        // [left...right] 之间所有以 right 结尾的子数组都符合“和 <= goal”
        count += right - left + 1
    }
    return count
}

使用说明

为什么原模板中“统计连续的0”比较复杂？
在滑动窗口中，如果存在 0，窗口的和不会改变，这会导致统计“确切”数量时变得棘手。“恰好为 K = 最多为 K - 最多为 K-1” 是处理此类滑动窗口问题最优雅的数学技巧。
核心优势：
- 哈希表法：时间 $O(N)$，空间 $O(N)$。适用于任何数组。
- 双指针法：时间 $O(N)$，空间 $O(1)$。仅适用于非负数组。
常见变形：
- 求和为 K 的子数组。
- 求奇数个数为 K 的子数组（将奇数看作 1，偶数看作 0）。

09. 单调递增栈

August 11, 2023 0 - 算法, 0.0 - 算法模版

正文

单调栈（Monotonic Stack）是一种极其重要的数据结构，专门用于解决“下一个更大元素（Next Greater Element）”或“上一个更小元素”这类问题。

算法模板 (寻找下一个更大元素)

fun nextGreaterElement(nums: IntArray): IntArray {
    val n = nums.size
    val result = IntArray(n) { -1 }
    // 栈中存储元素的索引（以便更新 result 数组）
    val stack = mutableListOf<Int>()

    for (i in nums.indices) {
        // 当栈不为空，且当前元素大于栈顶元素时
        while (stack.isNotEmpty() && nums[stack.last()] < nums[i]) {
            // 此时 nums[i] 就是栈顶元素的“下一个更大元素”
            val index = stack.removeAt(stack.size - 1)
            result[index] = nums[i]
        }
        
        // 当前元素入栈（等待属于它的更大元素出现）
        stack.add(i)
    }

    return result
}

使用说明

核心特性：
- 单调递增栈：栈内元素从底到顶单调递增。用于寻找右侧第一个比自己小的元素（或者左侧第一个比自己小的）。
- 单调递减栈：栈内元素从底到顶单调递减。用于寻找右侧第一个比自己大的元素（即模板写法）。
核心优势：
- 将 $O(N^2)$ 的暴力查找优化到 $O(N)$。每个元素最多进栈一次、出栈一次。
常见变形：
- 循环数组：通过遍历两次（i % n）来模拟循环。
- 接雨水：利用单调栈计算低洼处的面积。
- 最大矩形面积：利用单调栈寻找左右两侧的边界。
注意点：
- 明确题目要求的是“右侧第一个更大”还是“左侧第一个更小”。
- 明确栈里存的是“元素值”还是“元素的下标”（下标通常更通用）。

10. 二叉树-DFS (递归)

September 8, 2023 0 - 算法, 0.0 - 算法模版

正文

二叉树的深度优先搜索（DFS）递归写法是最直观的，其本质是利用了系统的函数调用栈。

算法模板

class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun dfs(root: TreeNode?) {
    // 递归终止条件
    if (root == null) return
    
    // 1. 先序遍历 (Pre-order): 根 -> 左 -> 右
    // visit(root)
    
    dfs(root.left)  
    
    // 2. 中序遍历 (In-order): 左 -> 根 -> 右
    // visit(root)
    
    dfs(root.right)  
    
    // 3. 后序遍历 (Post-order): 左 -> 右 -> 根
    // visit(root)
}

fun visit(node: TreeNode) {
    println(node.value)
}

使用说明

三种遍历顺序：
- 先序：常用于复制二叉树、序列化二叉树。
- 中序：二叉搜索树（BST）的中序遍历是有序序列。
- 后序：常用于计算二叉树的高度、删除二叉树。
核心优势：
- 逻辑极其简单，符合人类直觉。
- 代码量极少，易于实现。
性能分析：
- 时间复杂度：$O(N)$，每个节点访问一次。
- 空间复杂度：$O(H)$，其中 $H$ 是树的高度。最坏情况下（倾斜树）为 $O(N)$。
注意点：
- 递归必须有明确的终止条件（通常是 root == null）。
- 如果树的深度极大，可能会导致 StackOverflowError（栈溢出），此时需考虑迭代写法。