二分查找

使用条件:

  • 数组中元素是有序的
  • 注意: 若数组中存在重复元素, 那最后查找结果下标并不唯一

使用场景:

  • 在有序数组中寻找目标值的下标
  • 将目标值插入有序数组中
1
2
3
4
5
6
7
8
9
10
11
public int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {  // 因为是[left, right]左闭右闭, 因此必须判断等于的情况
        int mid = (left + right) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] > target) right = mid - 1;
        if (nums[mid] < target) left = mid + 1;
    }
    return -1;
}

双指针

介绍: 通过一个快指针和一个慢指针在一个for循环下完成两个for循环的工作

使用方法:

  • 同向移动
  • 双向移动

使用场景:

  • 原地移除数组中的某元素(同向)
  • 对有正有负的有序数组的元素平方再排序(双向)

滑动窗口

介绍: 不断调整窗口大小寻找所需结果(利用两个指针控制窗口大小)

使用场景:

  • 求满足条件的子序列

前缀和

介绍: 类似与哈夫曼编码的思想, 利用新数组保存每个数组元素i之前(包括i)的和

使用场景:

  • 对数组的区间和使用频繁的需求