1. 双指针法的核心思想
1.1 为什么选择双指针
在处理有序数组或需要线性扫描的场景时，双指针法能够以O(n)的时间复杂度完成常见任务，避免嵌套循环带来的高开销。通过维护两个指针来表示当前关注的区间，我们可以在不改变整体结构的情况下逐步逼近目标，保持空间复杂度为O(1)。这是一种“就地削减问题规模”的思考方式，常用于查找、匹配、去重等场景。
核心要点在于：定义好不变量，让两指针的移动规则与目标条件保持一致；遇到边界就收敛，避免无效遍历；以及在有序条件下，通过比较和调整指针位置快速缩小区间。
在实际编码中，双指针往往与有序性、滑动窗口、或区间和的计算结合，形成高效且优雅的解题模板。例如，处理有序数组中的两数之和，或在字符串/数组中查找对称性、重复元素等场景时，双指针都能发挥出色性能。
public class TwoPointer {
// 适用于有序数组，返回满足条件的两个下标
public int[] twoSumSorted(int[] numbers, int target) {
int i = 0, j = numbers.length - 1;
while (i < j) {
int sum = numbers[i] + numbers[j];
if (sum == target) return new int[]{i, j};
if (sum < target) i++;
else j--;
}
return new int[]{-1, -1};
}
}2. 哈希表在数组题中的高效应用
2.1 哈希表的基本原理
当问题涉及快速查找“缺失值、配对值”时，哈希表提供常数平均时间的查找能力，使得原本需要两层循环的检查转为一遍遍历完成。通过把已看到的数字作为键、其下标或出现次数作为值，我们能够在O(n)时间内定位匹配项，大幅降低时间复杂度，且空间复杂度通常为O(n)。
在数组问题中，哈希表是实现“快速配对”的利器，例如经典的两数之和、子数组和目标值的判定等场景，往往能够通过一个Map实现最优解。
import java.util.HashMap;
import java.util.Map;
public class TwoSumHash {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (map.containsKey(need)) {
return new int[]{map.get(need), i};
}
map.put(nums[i], i);
}
return new int[]{-1, -1};
}
}3. 滑动窗口：高效求解子数组问题
3.1 滑动窗口的应用场景与模板
滑动窗口是一种在固定或动态窗口内维护子数组信息的技术，适用于长度约束、子数组和、无重复子数组等问题。通过在每次移动窗口时增减边界元素，我们可以在O(n)时间内完成计算，且不需要重新计算整段区间和，从而获得高效的解法。
使用滑动窗口时，重要的是设计好数据结构来维护窗口内的统计信息（如和、最大值、出现次数等），并确保窗口移动的条件和更新步骤保持一致性，以避免遗漏或重复计算。
public class SlidingWindow {
// 固定大小窗口，求最大和
public int maxSumSubarrayOfSizeK(int[] arr, int k) {
if (arr == null || arr.length < k) return 0;
int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
int maxSum = windowSum;
for (int i = k; i < arr.length; i++) {
windowSum += arr[i] - arr[i - k];
if (windowSum > maxSum) maxSum = windowSum;
}
return maxSum;
}
}4. 排序、分治与并行思维在数组中的应用
4.1 归并排序与分治的核心要点
排序与分治思想是处理大规模数组问题的强力工具。归并排序通过将问题不断拆解为左右两段，最终在合并阶段实现排序，其时间复杂度为O(n log n)，空间复杂度为O(n)。在解决“合并、有序性、去重”等问题时，分治模板能够提供稳定、可读的解法。
实现归并排序时，关注点在于：分割、排序子段、以及稳定地合并两个有序段。良好的实现有助于后续在数组题中，利用“部分有序”的特性提升优化空间与时间表现。
public class MergeSort {
public void sort(int[] arr) {
if (arr == null || arr.length < 2) return;
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
}
private void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid, temp);
mergeSort(arr, mid + 1, right, temp);
merge(arr, left, mid, right, temp);
}
private void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
for (int idx = left; idx <= right; idx++) arr[idx] = temp[idx];
}
}5. 动态规划与数组题的结合
5.1 子数组最大和的DP解法（Kadane算法）
动态规划在数组题中的典型应用是将问题拆解为“以当前位置结尾的最优解”与“全局最优解”两种状态，Kadane算法就是最经典的线性DP范例，通过在遍历过程中更新两个变量，得到整个数组的最大子数组和。
核心思想是：要么把当前元素加入前缀子数组，要么从当前元素重新开始，以此来维护连续子数组的最大和，并在遍历结束时返回全局最大值。
public class Kadane {
// 最大子数组和（连续子数组）
public int maxSubArray(int[] nums) {
int maxEndingHere = nums[0];
int maxSoFar = nums[0];
for (int i = 1; i < nums.length; i++) {
maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
}5.2 前缀和与快速区间查询
前缀和是一种强大的技巧，把区间和问题转化为前缀差的计算，从而在多次查询时实现O(1)时间复杂度的区间和计算。配合动态规划，可以快速分析更复杂的子数组模式，例如寻找最大区间和、最小子数组长度等。
在实现时，可以先构建前缀和数组，然后通过对比前缀差来得到任意区间的和，避免重复累加，提升性能，也便于和滑动窗口、分治等模板结合使用。
public class PrefixSum {
public int[] maxSubArrayPrefixSum(int[] nums) {
int n = nums.length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
max = Math.max(max, prefix[j + 1] - prefix[i]);
}
}
return new int[]{max};
}
}