这里写目录标题
1. 两数之和
题目介绍
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
- 2 <= nums.length <= 103
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- 只会存在一个有效答案
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{
i, j};
}
}
}
return new int[0];
}
}
注意到上一个解法的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。
因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。
我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (hashMap.containsKey(target - nums[i])) {
return new int[]{
hashMap.get(target - nums[i]), i};
}
hashMap.put(nums[i], i);
}
return new int[0];
}
}
164. 最大间距
题目介绍
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
示例 1：
输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2：
输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。
说明：
- 你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
- 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-gap
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
我们先对传入的数组进行临界检查，然后对数组进行排序，排序直接调用库函数就行了。
然后从左向右依次两两比较，找出最大的那个间距，然后重新赋值给 maxSpace 就行了。
class Solution {
public int maximumGap(int[] nums) {
if (nums == null || nums.length < 2) return 0;
Arrays.sort(nums);
int maxSpace = 0;
for (int i = 1; i < nums.length; i++) {
maxSpace = Math.max(maxSpace, nums[i] - nums[i - 1]);
}
return maxSpace;
}
}
240. 搜索二维矩阵 II
题目介绍
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。
该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
示例 2：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false
提示：
- m == matrix.length
- n == matrix[i].length
- 1 <= n, m <= 300
- -109 <= matix[i][j] <= 109
- 每行的所有元素从左到右升序排列
- 每列的所有元素从上到下升序排列
- -109 <= target <= 109
相同题目：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
如果 target = 5，我们来看看在不使用暴力搜索的情况下，如何快速查找。
从右上角开始查找，15>5，因此，我们需要向左移动。为什么不向下移动，因为，向下的数都比15大。
向左移动完毕之后，11>5，因此，我们需要向左移动。为什么不向下移动，因为，向下的数都比11大。
向左移动完毕之后，7>5，因此，我们需要向左移动。为什么不向下移动，因为，向下的数都比7大。
向左移动完毕之后，4<5，因此，我们需要向下移动。为什么不向左移动，因为，向左的数都比4小。
向下移动完毕之后，5=5，因此，我们需要返回true。
可能上面的步骤不是很难理解，但有人可能会想，为啥不从左上角的 1 开始搜索呢？原因很简单，左上角的 1 下边都是比 1 大的，左上角的 1 右边都是比 1 大的，两个都是大的，你咋知道该下还是垓右，同理，右下角的 30 也类似，向左看都比 30 小，向上看都比 30 小。两个都是小的，你咋知道该左还是垓上，因此，只有从左下角的18处或者右上角的15处开始搜索才是正解。因为当target大于、小于、等于当前数组元素值时，都有方向可以走，没有歧义。
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
// 临界检查
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
// 获取行数
int rows = matrix.length;
// 获取列数
int cols = matrix[0].length;
// 定义行指针
int row = 0;
// 定义列指针（从右上角开始搜索）
int col = cols - 1;
// 循环搜索
while ((row >= 0 && row < rows) && (col >= 0 && col < cols)) {
if (target > matrix[row][col]) {
row++;
} else if (target < matrix[row][col]) {
col--;
} else {
return true;
}
}
// 没有找到
return false;
}
}
26. 删除有序数组中的重复项
题目介绍
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明：
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ，并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示：
- 0 <= nums.length <= 3 * 104
- -104 <= nums[i] <= 104
- nums 已按升序排列
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
定义两个指针，一个指针用于从左向右依次扫描，我们称为fast快指针，另一个指针用于存储不重复的数字，由于移动较慢，我们称为slow慢指针。在定义之初，slow应该从0开始，而fast却不必从0开始，自己和自己比较这是不明智的，如下图：
开始第一轮比较，快指针所指向的元素和慢指针所指向的元素相等，则快指针直接后移即可。
开始再一次比较，快指针所指向的元素和慢指针所指向的元素不等，则慢指针加加，然后把快指针所指向的元素放入慢指针所指向的位置，快指针直接后移即可。
按照上边这种模式一直向后扫描，直到快指针全部扫描完，最终的结果也就出来了，但是我们返回的时候，由于慢指针是下标，并不代表新数组的长度，因此需要加一再返回。
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int slow = 0;
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
nums[++slow] = nums[fast];
}
}
return slow + 1;
}
}
27. 移除元素
题目介绍
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明：
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示：
- 0 <= nums.length <= 100
- 0 <= nums[i] <= 50
- 0 <= val <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
定义两个指针，一个指针用于从左向右依次扫描，我们称为fast快指针，另一个指针用于存储和 val 不相同的数字，由于移动较慢，我们称为slow慢指针。在定义之初，slow应该从0开始，而fast也必须从0开始，如下图：
如果 val = 2，开始进行第一轮循环，快指针所指向的元素和val不相等，则应该把快指针对应的元素拷贝到慢指针所对应的位置处，然后快指针加加、慢指针加加。
同理，快指针所指向的元素和val不相等，则应该把快指针对应的元素拷贝到慢指针所对应的位置处，然后快指针加加、慢指针加加。
此时，快指针所指向的元素和val相等，则快指针直接加加即可。
此时，快指针所指向的元素和val相等，则快指针直接加加即可。
现在，快指针所指向的元素和val不相等，则应该把快指针对应的元素拷贝到慢指针所对应的位置处，然后快指针加加、慢指针加加。
按照上边这种模式，快指针一直向后扫描，直到全部扫描完毕，最终结果就出来了，慢指针所对应的就是新数组的大小。
class Solution {
public int removeElement(int[] nums, int val) {
if (nums.length == 0) return 0;
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != val) {
nums[slow++] = nums[fast];
}
}
return slow;
}
}
75. 颜色分类
题目介绍
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用 整数 0、 1 和 2 分别表示红色、白色和蓝色。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
示例 3：
输入：nums = [0]
输出：[0]
示例 4：
输入：nums = [1]
输出：[1]
提示：
- n == nums.length
- 1 <= n <= 300
- nums[i] 为 0、1 或 2
进阶：
- 你可以不使用代码库中的排序函数来解决这道题吗？
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
解决这道题，扫描一遍，只需要把0放到数组的左边，把2放到数组的右边就行了。因此，我们至少需要定义两个指针，一个指针用来存放0，另一个指针用来存放2，除了这两个指针，我们还需要一个指针从左到右进行扫描，因此是三指针。
从左向右依次扫描，当遇到元素为2的时候，交换黑色和蓝色指针所指向的值，然后蓝色指针减减。
但是在这里要注意，有可能蓝色指针指向的位置也是一个2，这样交换了位置之后，我们还需要再进行一次判断。
交换前（换了一个图）：
交换后（上图交换后）：
我们针对上图的情况，需要进行再次判断，如果此时黑色指针指向的还是2，那就让他和蓝色指针所指向的值交换，然后蓝色指针减减、黑色指针加加。
如果扫描时遇到的是0，则让黑色指针所指向的值和绿色指针所指向的值进行交换，然后绿色指针加加、黑色指针加加。
此时黑色指针扫描遇到的仍旧是2，则与蓝色指针所指向的值进行交换，然后蓝色指针减减，再然后进行二次判断。
再进行二次判断的时候，发现黑色指针所指向的值是1，1既不用放到数组左边也不用放到数组右边，所以直接跳过，即黑色指针加加。
此时我们发现数组中元素已然有序，则结束条件就是黑色指针 大于 蓝色指针的时候退出循环。
class Solution {
public void sortColors(int[] nums) {
int i = 0; //扫描
int l = 0; //放零
int r = nums.length - 1; //放二
while (i <= r) {
if (nums[i] == 0) {
swap(nums, l++, i++);
} else if (nums[i] == 1) {
i++;
} else {
swap(nums, r--, i);
}
}
}
/**
* 交换数组中元素
*
* @param nums 数组
* @param i1 索引1
* @param i2 索引2
*/
public void swap(int[] nums, int i1, int i2) {
int tmp = nums[i1];
nums[i1] = nums[i2];
nums[i2] = tmp;
}
}
977. 有序数组的平方
题目介绍
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
提示：
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums 已按 非递减顺序 排序
进阶：
- 请你设计时间复杂度为
O(n)的算法解决本问题。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
解决这道题的思路主要是定义两个指针，分别指向平方后的第一个元素和最后一个元素，然后再定义一个新数组。
判断这两个指针所指向的元素哪一个大，把大的值存放到新数组中，然后指向大的元素一方的指针移动，新数组的指针减减即可。
class Solution {
public int[] sortedSquares(int[] nums) {
// 创建新的数组
int[] tmps = new int[nums.length];
// 定义三个指针
int i = nums.length - 1;
int l = 0;
int r = nums.length - 1;
while (l <= r) {
if (nums[l] * nums[l] >= nums[r] * nums[r]) {
tmps[i--] = nums[l] * nums[l++];
} else {
tmps[i--] = nums[r] * nums[r--];
}
}
// 返回最终结果
return tmps;
}
}
剑指 Offer 03. 数组中重复的数字
题目介绍
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
- 2 <= n <= 100000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
我们可以利用 set 集合元素不能重复这一特点，循环遍历数组元素，依次加入到 set 集合中，如果加入失败，就代表该数字重复。
class Solution {
public int findRepeatNumber(int[] nums) {
HashSet<Integer> hashSet = new HashSet<>();
for (int num : nums) {
if (!hashSet.add(num)) {
return num;
}
}
return -1;
}
}
10.01. 合并排序的数组
题目介绍
给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。
示例：
输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
说明：
- A.length == n + m
相同题目：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sorted-merge-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
定义三个指针，一个指针指向A数组有效数据的最后一个元素，一个指针指向B数组的最后一个元素，还有一个指针指向A数组的最后一个元素。具体实现思路就是，比较绿色指针和橙色指针所对应的数据的大小，拿出较大的值放到黑色指针所指的地方，然后指针减减。
在这个过程中，橙色指针的结束条件就是 bi >= 0，绿色指针也应该满足 ai >= 0，最终实现的代码如下：
class Solution {
public void merge(int[] A, int m, int[] B, int n) {
int ai = m - 1;
int bi = n - 1;
int cur = A.length - 1;
while (bi >= 0) {
if (ai >= 0 && A[ai] > B[bi]) {
A[cur--] = A[ai--];
} else {
A[cur--] = B[bi--];
}
}
}
}
16.16. 部分排序
题目介绍
给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。
示例：
输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
输出： [3,9]
提示：
- 0 <= len(array) <= 1000000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sub-sort-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目实现
我们首先从左向右依次扫描，遇到比 max 还大的值就直接记录下来，说明从左向右是升序，如果一旦遇到比 max 的值小的，说明这个位置是需要排序的位置，按照这个模式从左向右扫描完一遍，就能找到区间 n 的值。
我们然后从右向左依次扫描，遇到比 min 还小的值就直接记录下来，说明从右向左是降序，如果一旦遇到比 min 的值大的，说明这个位置是需要排序的位置，按照这个模式从右向左扫描完一遍，就能找到区间 m 的值。
除了上边的解题思路，还需要注意，数组的长度可能为0，因此，我们需要对数组的长度进行判断。
class Solution {
public int[] subSort(int[] array) {
if (array.length == 0) return new int[]{
-1, -1};
// 从左向右扫描逆序对的右下标（正序，从小到大）
int max = array[0];
int r = -1;
for (int i = 1; i < array.length; i++) {
if (array[i] >= max) {
max = array[i];
} else {
r = i;
}
}
// 如果从左到右扫描发现没有找到需要排序的位置则返回
if (r == -1) return new int[]{
-1, -1};
// 从右向左扫描逆序对的左下标（逆序，从大到小）
int min = array[array.length - 1];
int l = -1;
for (int i = array.length - 2; i >= 0; i--) {
if (array[i] <= min) {
min = array[i];
} else {
l = i;
}
}
return new int[]{
l, r};
}
}
转载：https://blog.csdn.net/qq_38490457/article/details/117378145