15. 三数之和

一、题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

16. 最接近的三数之和

一、题目描述

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和

假定每组输入只存在唯一答案。

• 3 <= nums.length <= 10^3
• -10^3 <= nums[i] <= 10^3
• -10^4 <= target <= 10^4

6186. 按位或最大的最小子数组长度

一、题目描述

给你一个长度为 n 下标从 0 开始的数组 nums ，数组中所有数字均为非负整数。

对于 0 到 n - 1 之间的每一个下标 i ，你需要找出 nums 中一个 最小 非空子数组，它的起始位置为 i （包含这个位置），同时有 最大 的 按位或运算值 。

换言之，令 Bij 表示子数组 nums[i…j] 的按位或运算的结果，你需要找到一个起始位置为 i 的最小子数组，这个子数组的按位或运算的结果等于 max(Bik) ，其中 i <= k <= n - 1 。

线段树

一、线段树是什么？

• 线段树本质上是一种缓存，它缓存的是区间值
• 线段树一棵平衡二叉树
• 线段树的节点表示的是一个区间，节点值表示区间值

二分查找

一、代码模板

常见的二分查找模板代码如下：

1
2
3
4
5
6
7
8
9
10

left = low, right = high;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (满足条件) {
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}
return left; // 或 right

在二分查找中，有几个需要注意的地方：

基数排序

一、算法描述

1.1 核心思想

• 数据有高低位之分，位之间有递进关系
• 高位相等的情况下，才去对比低位大小
• 按照低位到高位的顺序，使用稳定排序算法对每一位排序

1.2 细节解释

桶排序

一、算法描述

1.1 核心思想

• 把不同范围的数据划分到不同的桶中
• 桶与桶之间是有序的，桶间无需排序
• 只需要对桶内的数据排序

1.2 细节解释

计数排序

一、算法描述

1.1 核心思想

• 计数排序是桶大小为 1 的桶排序的一种特殊情况
• 由于桶大小为 1，所以桶内都是相同的值
• 桶内都是相同的值，无需桶内排序，只需要记录数据频率
• 最后排序时，按照数据频率将数据填充回原数组

1.2 细节解释

归并排序

一、算法描述

1.1 核心思想

• 二分，将数据二等均分，然后分别排序，再合并2个排好序的数据
• 递归，一直二等均分数据，直到无法分割后，才开始递归合并返回
• 整个二分和合并的过程类似于一棵二叉树，从下往上合并数据，先对子树排序，再合并成根节点

1.2 细节解释

冒泡和插入对比

一、比较次数

冒泡排序比较：