前缀和算法通过预处理构建o(n)时间复杂度的前缀和数组，使任意子数组区间和查询降至o(1)，适用于静态数组的多次求和、平均值及满足条件的连续子段统计等场景。
一维数组是 Java 中最基础的数据结构，但要高效实现复杂查询（比如范围查找、Top-K、区间统计等），光靠简单遍历远远不够。关键在于结合算法思想与数组特性，用合适策略减少时间开销、避免重复计算。
预处理：构建前缀和或排序索引提升查询效率
对静态或低频更新的一维数组，预处理能将多次查询的总体复杂度大幅降低。例如求任意子数组和，暴力法每次 O(n)，而构建前缀和数组后可降至 O(1) 查询。
- 前缀和适用于求和、平均值、满足条件的连续子段数量等场景；构造时注意边界处理（如 prefix[0] = 0，prefix[i] = prefix[i-1] + arr[i-1]）
- 若需频繁按值查找（如找大于某阈值的第一个位置），可先排序并保存原始下标映射，再用二分搜索 —— 注意区分“值有序”和“位置有序”
- 对于含重复元素的数组，使用 TreeMap
> 记录每个值对应的所有下标，支持快速定位所有匹配位置
双指针技巧：在线性时间内完成区间类查询
当查询逻辑涉及两个约束（如“和最接近目标值的子数组”“最长无重复元素子序列”），双指针比嵌套循环更简洁高效，且无需额外空间。
- 左右指针同向移动，维护一个滑动窗口；右指针扩展时更新状态（如累加和、哈希计数），左指针收缩时校验并更新最优解
- 适用于数组已排序或可排序的场景（如两数之和变形、最小覆盖子串逻辑迁移）
- 注意终止条件：通常右指针到末尾即停，但某些问题（如找固定长度最大和）只需一次遍历即可
二分搜索变体：突破“必须有序”的思维定式
二分不只是找某个值 —— 它本质是利用单调性在 O(log n) 内定位临界点。即使原数组无序，也可对答案空间或变换后序列做二分。
- 例如“最小化最大子数组和”，枚举答案范围（left = max(arr), right = sum(arr)），每次用贪心验证能否划分出 ≤ k 个子数组
- 对已排序数组查上界/下界（如 Arrays.binarySearch 返回负值时的插入点），可直接用 Arrays 或手写 lowerBound / upperBound
- 注意整数溢出：计算中点改用 left + (right - left) / 2，尤其当数组长度接近 Integer.MAX_VALUE 时
离线查询 + 排序：批量处理比单次优化更有效
当多个查询可预先获知（如 LeetCode 的“区间和检索”带修改，或“查询区间内第 K 小元素”），把查询排序后统一处理，常比逐个响应快得多。
- 莫队算法适合离线、无修改、基于区间的统计类查询（如区间众数、异或和），核心是分块+排序查询，均摊 O(n√n)
- 离线+树状数组/线段树：将数值离散化，按查询右端点排序，边插入边回答——适合“右侧截止的区间内满足条件的元素个数”类问题
- 简单场景下，把所有查询按右边界排序，配合双指针+HashMap 统计，也能避免重复扫描
不复杂但容易忽略：数组查询性能瓶颈往往不在循环本身，而在数据组织方式和查询模式是否匹配。动手前先问一句——这个查询会被调多少次？数组会变吗？结果需要精确还是近似？想清楚，再选策略。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
