力扣刷题：数组篇

梦里梦外; 2022-10-16 09:40 327阅读 1赞

### 目录 ###

*  1. 两数之和
 *   *  题目介绍
     *  题目实现
 *  11. 盛最多水的容器
 *   *  题目介绍
     *  题目实现
 *  164. 最大间距
 *   *  题目介绍
     *  题目实现
 *  240. 搜索二维矩阵 II
 *   *  题目介绍
     *   *   *  \[剑指 Offer 04. 二维数组中的查找\](https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/)
     *  题目实现
 *  26. 删除有序数组中的重复项
 *   *  题目介绍
     *  题目实现
 *  27. 移除元素
 *   *  题目介绍
     *  题目实现
 *  75. 颜色分类
 *   *  题目介绍
     *  题目实现
 *  88. 合并两个有序数组
 *   *  题目介绍
     *  题目实现
 *  977. 有序数组的平方
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 03. 数组中重复的数字
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 04. 二维数组中的查找
 *   *  题目介绍
     *   *   *  \[240. 搜索二维矩阵 II\](https://leetcode-cn.com/problems/search-a-2d-matrix-ii/)
     *  题目实现
 *  剑指 Offer 10- I. 斐波那契数列
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 10- II. 青蛙跳台阶问题
 *   *  题目介绍
     *   *   *  \[70. 爬楼梯\](https://leetcode-cn.com/problems/climbing-stairs/)
     *  题目实现
 *  剑指 Offer 11. 旋转数组的最小数字
 *   *  题目介绍
     *   *   *  \[154. 寻找旋转排序数组中的最小值 II\](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/)
     *  题目实现
 *  剑指 Offer 16. 数值的整数次方
 *   *  题目介绍
     *   *   *  \[50. Pow(x, n)\](https://leetcode-cn.com/problems/powx-n/)
     *  题目实现
 *  10.01. 合并排序的数组
 *   *  题目介绍
     *   *   *  \[88. 合并两个有序数组\](https://leetcode-cn.com/problems/merge-sorted-array/)
     *  题目实现
 *  16.16. 部分排序
 *   *  题目介绍
     *  题目实现

--------------------

# 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];
        }
    }

# 11. 盛最多水的容器 #

## 题目介绍 ##

给你 n 个非负整数 `a1，a2，...，an`，每个数代表坐标中的一个点 `(i, ai)`。在坐标内画 `n` 条垂直线，垂直线 `i` 的两个端点分别为 `(i, ai)`和 `(i, 0)` 。找出其中的两条线，使得它们与 `x` 轴共同构成的容器可以容纳最多的水。

**说明：** 你不能倾斜容器。

**示例 1：**

![b72da16967684cb3b15da697955ea947.png][]

输入：[1,8,6,2,5,4,8,3,7]
    输出：49 
    解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

**示例 2：**

输入：height = [1,1]
    输出：1

**示例 3：**

输入：height = [4,3,2,1,4]
    输出：16

**示例 4：**

输入：height = [1,2,1]
    输出：2

**提示：**

*  n = height.length
 *  2 <= n <= 3 \* 104
 *  0 <= height\[i\] <= 3 \* 104

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/container-with-most-water  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

设置双指针 `i,j` 分别位于容器壁两端，根据规则移动指针（后续说明），并且更新面积最大值 `res`，直到 `i == j` 时返回 `res`。

每次选定围成水槽两板高度 `h[i],h[j]` 中的短板，向中间收窄 `1` 格。以下证明：

设每一状态下水槽面积为 `S(i, j),(0 <= i < j < n)`，由于水槽的实际高度由两板中的短板决定，则可得面积公式`S(i,j)=min(h[i],h[j])×(j−i)`。

在每一个状态下，无论长板或短板收窄 `1` 格，都会导致水槽 **底边宽度** \-1：

*  若向内移动短板，水槽的短板 `min(h[i],h[j])` 可能变大，因此水槽面积 `S(i,j)` 可能增大。
 *  若向内移动长板，水槽的短板 `min(h[i],h[j])` 不变或变小，下个水槽的面积一定小于当前水槽面积。

但无论哪种情况，向内收缩并不会 **不会导致丢失面积最大值** 。

class Solution { 
        public int maxArea(int[] height) { 
            int i = 0, j = height.length - 1, res = 0;
            while (i < j) { 
                res = height[i] < height[j] ?
                        Math.max(res, (j - i) * height[i++]) :
                        Math.max(res, (j - i) * height[j--]);
            }
            return res;
        }
    }

# 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：**

![9c7e92b26f6c83b0eb3fe8a9084cf71f.png][]

输入：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：**

![a54b9f7e54ee4ebbc3d14f2ee4d196fb.png][]

输入：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

**相同题目：**

*  #### [剑指 Offer 04. 二维数组中的查找][Offer 04.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

如果 `target = 5`，我们来看看在不使用暴力搜索的情况下，如何快速查找。

从右上角开始查找，`15>5`，因此，我们需要向左移动。为什么不向下移动，因为，向下的数都比15大。

![bd93575c0908efc3548a1d757720b38c.png][]

向左移动完毕之后，`11>5`，因此，我们需要向左移动。为什么不向下移动，因为，向下的数都比11大。

![14a4a2ec2b990591c8f725460e04c3ed.png][]

向左移动完毕之后，`7>5`，因此，我们需要向左移动。为什么不向下移动，因为，向下的数都比7大。

![3e4d4154be5fe8d9868259ef6c57dc5e.png][]

向左移动完毕之后，`4<5`，因此，我们需要向下移动。为什么不向左移动，因为，向左的数都比4小。

![c8710acc1515262c469ecd56f241c541.png][]

向下移动完毕之后，`5=5`，因此，我们需要返回true。

![2fac973f6367147085e1d776a1453d02.png][]

可能上面的步骤不是很难理解，但有人可能会想，为啥不从左上角的 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开始，自己和自己比较这是不明智的，如下图：

![04ddb062aa5c02f6049c8dbe301ffee5.png][]

开始第一轮比较，快指针所指向的元素和慢指针所指向的元素相等，则快指针直接后移即可。

![7646f4a6cdb192c1a0fbb3491ec03a9c.png][]

开始再一次比较，快指针所指向的元素和慢指针所指向的元素不等，则慢指针加加，然后把快指针所指向的元素放入慢指针所指向的位置，快指针直接后移即可。

![451cc5b18903bdf421f83e56c65111a2.png][]

按照上边这种模式一直向后扫描，直到快指针全部扫描完，最终的结果也就出来了，但是我们返回的时候，由于慢指针是下标，并不代表新数组的长度，因此需要加一再返回。

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开始，如下图：

![827ae36a7e7c172322bb0bf070685904.png][]

如果 val = 2，开始进行第一轮循环，快指针所指向的元素和val不相等，则应该把快指针对应的元素拷贝到慢指针所对应的位置处，然后快指针加加、慢指针加加。

![3ba5db85b1e2a087cad849bc3d9132f0.png][]

同理，快指针所指向的元素和val不相等，则应该把快指针对应的元素拷贝到慢指针所对应的位置处，然后快指针加加、慢指针加加。

![c4dc2ceee930c056a87c8778293e74ce.png][]

此时，快指针所指向的元素和val相等，则快指针直接加加即可。

![85ccc2607dda22aef618848d15db2b93.png][]

此时，快指针所指向的元素和val相等，则快指针直接加加即可。

![1e8df68365748a72fa28651b0146b164.png][]

现在，快指针所指向的元素和val不相等，则应该把快指针对应的元素拷贝到慢指针所对应的位置处，然后快指针加加、慢指针加加。

![60499d2d0cad6532626130fb91c6ce97.png][]

按照上边这种模式，快指针一直向后扫描，直到全部扫描完毕，最终结果就出来了，慢指针所对应的就是新数组的大小。

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，除了这两个指针，我们还需要一个指针从左到右进行扫描，因此是三指针。

![aca3f14f58674cbbb6fbad175f9e3b05.png][]

从左向右依次扫描，当遇到元素为2的时候，交换黑色和蓝色指针所指向的值，然后蓝色指针减减。

但是在这里要注意，有可能蓝色指针指向的位置也是一个2，这样交换了位置之后，我们还需要再进行一次判断。

交换前（换了一个图）：

![1126d3c72ea3a993482019327b6d14bf.png][]

交换后（上图交换后）：

![79d6c44ea8d6c87ee6665312816d65eb.png][]

我们针对上图的情况，需要进行再次判断，如果此时黑色指针指向的还是2，那就让他和蓝色指针所指向的值交换，然后蓝色指针减减、黑色指针加加。

![ac4c67d9ec89c3f0b825aa11119c2ee1.png][]

如果扫描时遇到的是0，则让黑色指针所指向的值和绿色指针所指向的值进行交换，然后绿色指针加加、黑色指针加加。

![f68f1d6f279d6010b1d925d7a592d495.png][]

此时黑色指针扫描遇到的仍旧是2，则与蓝色指针所指向的值进行交换，然后蓝色指针减减，再然后进行二次判断。

![b0a92cf6d191867c6a4a13081e4bf899.png][]

再进行二次判断的时候，发现黑色指针所指向的值是1，1既不用放到数组左边也不用放到数组右边，所以直接跳过，即黑色指针加加。

![303e5f5e2cd1b19e154ec5de7f78a267.png][]

此时我们发现数组中元素已然有序，则结束条件就是黑色指针 **大于** 蓝色指针的时候退出循环。

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;
        }
    }

# 88. 合并两个有序数组 #

## 题目介绍 ##

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

**示例 1：**

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
    输出：[1,2,2,3,5,6]
    解释：需要合并 [1,2,3] 和 [2,5,6] 。
    合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

**示例 2：**

输入：nums1 = [1], m = 1, nums2 = [], n = 0
    输出：[1]
    解释：需要合并 [1] 和 [] 。
    合并结果是 [1] 。

**示例 3：**

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
    输出：[1]
    解释：需要合并的数组是 [] 和 [1] 。
    合并结果是 [1] 。
    注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

**提示：**

*  nums1.length == m + n
 *  nums2.length == n
 *  0 <= m, n <= 200
 *  1 <= m + n <= 200
 *  \-109 <= nums1\[i\], nums2\[j\] <= 109

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/merge-sorted-array  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public void merge(int[] nums1, int m, int[] nums2, int n) { 
            for (int i = 0; i < n; i++) { 
                nums1[m + i] = nums2[i];
            }
            Arrays.sort(nums1);
        }
    }

# 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  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![b1eb018bef0ed95a3284d70bfee3adf8.png][]

解决这道题的思路主要是定义两个指针，分别指向平方后的第一个元素和最后一个元素，然后再定义一个新数组。

![9f06544720aa9008d95ccd6347e2f02e.png][]

判断这两个指针所指向的元素哪一个大，把大的值存放到新数组中，然后指向大的元素一方的指针移动，新数组的指针减减即可。

![d8db0afc5176180435c192473c9ee6cd.png][]

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;
        }
    }

# 剑指 Offer 04. 二维数组中的查找 #

## 题目介绍 ##

在一个 n \* m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

**示例：**

现有矩阵 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。

给定 target = 20，返回 false。

**限制：**

*  0 <= n <= 1000
 *  0 <= m <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

**相同题目：**

*  #### [240. 搜索二维矩阵 II][240. _ II] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

如果 `target = 5`，我们来看看在不使用暴力搜索的情况下，如何快速查找。

从右上角开始查找，`15>5`，因此，我们需要向左移动。为什么不向下移动，因为，向下的数都比15大。

![bd93575c0908efc3548a1d757720b38c.png][]

向左移动完毕之后，`11>5`，因此，我们需要向左移动。为什么不向下移动，因为，向下的数都比11大。

![14a4a2ec2b990591c8f725460e04c3ed.png][]

向左移动完毕之后，`7>5`，因此，我们需要向左移动。为什么不向下移动，因为，向下的数都比7大。

![3e4d4154be5fe8d9868259ef6c57dc5e.png][]

向左移动完毕之后，`4<5`，因此，我们需要向下移动。为什么不向左移动，因为，向左的数都比4小。

![c8710acc1515262c469ecd56f241c541.png][]

向下移动完毕之后，`5=5`，因此，我们需要返回true。

![2fac973f6367147085e1d776a1453d02.png][]

# 剑指 Offer 10- I. 斐波那契数列 #

## 题目介绍 ##

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1
    F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

**示例 1：**

输入：n = 2
    输出：1

**示例 2：**

输入：n = 5
    输出：5

**提示：**

*  0 <= n <= 100

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

解法一：数组版

class Solution { 
        public int fib(int n) { 
            if (n <= 1) return n;
            int[] dp = new int[n + 1];
            dp[0] = 0;
            dp[1] = 1;
            for (int i = 2; i < n + 1; i++) { 
                dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
            }
            return dp[n];
        }
    }

解法二：变量版

class Solution { 
        public int fib(int n) { 
            if (n <= 1) return n;
            int n1 = 0, n2 = 0, r = 1;
            for (int i = 2; i < n + 1; i++) { 
                n1 = n2;
                n2 = r;
                r = (n1 + n2) % 1000000007;
            }
            return r;
        }
    }

# 剑指 Offer 10- II. 青蛙跳台阶问题 #

## 题目介绍 ##

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

**示例 1：**

输入：n = 2
    输出：2

**示例 2：**

输入：n = 7
    输出：21

**示例 3：**

输入：n = 0
    输出：1

**提示：**

*  0 <= n <= 100

**相同题目：**

*  #### [70. 爬楼梯][70.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public int numWays(int n) { 
            if (n <= 1) return 1;
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
            for (int i = 2; i < n + 1; i++) { 
                dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
            }
            return dp[n];
        }
    }

# 剑指 Offer 11. 旋转数组的最小数字 #

## 题目介绍 ##

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 \[3,4,5,1,2\] 为 \[1,2,3,4,5\] 的一个旋转，该数组的最小值为1。

**示例 1：**

输入：[3,4,5,1,2]
    输出：1

**示例 2：**

输入：[2,2,2,0,1]
    输出：0

**相同题目：**

*  #### [154. 寻找旋转排序数组中的最小值 II][154. _ II] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

解法一：排序

class Solution { 
        public int minArray(int[] numbers) { 
            Arrays.sort(numbers);
            return numbers[0];
        }
    }

解法二：遍历

class Solution { 
        public int minArray(int[] numbers) { 
            int min = numbers[0];
            for (int i = 0; i < numbers.length; i++) { 
                if (min > numbers[i]) { 
                    min = numbers[i];
                }
            }
            return min;
        }
    }

# 剑指 Offer 16. 数值的整数次方 #

## 题目介绍 ##

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

**示例 1：**

输入：x = 2.00000, n = 10
    输出：1024.00000

**示例 2：**

输入：x = 2.10000, n = 3
    输出：9.26100

**示例 3：**

输入：x = 2.00000, n = -2
    输出：0.25000
    解释：2-2 = 1/22 = 1/4 = 0.25

**提示：**

*  \-100.0 < x < 100.0
 *  \-231 <= n <= 231\-1
 *  \-104 <= xn <= 104

**相同题目：**

*  #### [50. Pow(x, n)][50. Pow_x_ n] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![37c7fecb1af4ac86a40cc94f02fe04a5.png][]

class Solution { 
        public double myPow(double x, int n) { 
            if (x == 0) return 0;
            double res = 1.00;
            long b = n;
            if (b < 0) { 
                x = 1 / x;
                b = -b;
            }
            while (b > 0) { 
                if ((b & 1) == 1) { 
                    res *= x;
                }
                x *= x;
                b >>= 1;
            }
            return res;
        }
    }

# 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

**相同题目：**

*  #### [88. 合并两个有序数组][88.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/sorted-merge-lcci  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![b85b90fb2f833c14e5cffc92b949c247.png][]

定义三个指针，一个指针指向A数组有效数据的最后一个元素，一个指针指向B数组的最后一个元素，还有一个指针指向A数组的最后一个元素。具体实现思路就是，比较绿色指针和橙色指针所对应的数据的大小，拿出较大的值放到黑色指针所指的地方，然后指针减减。

![861c0ce50c104b2289f35f332f43154d.png][]

在这个过程中，橙色指针的结束条件就是 `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 的值。

![4ff3f2415062bacee7a973afda2270a0.png][]

我们然后从右向左依次扫描，遇到比 min 还小的值就直接记录下来，说明从右向左是降序，如果一旦遇到比 min 的值大的，说明这个位置是需要排序的位置，按照这个模式从右向左扫描完一遍，就能找到区间 m 的值。

![2ad2fa95f949f1b78087a212f10ac658.png][]

除了上边的解题思路，还需要注意，数组的长度可能为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};
        }
    }

[b72da16967684cb3b15da697955ea947.png]: /images/20221014/747b22d6de1544868e8a5cf8bcc2d7fe.png
[9c7e92b26f6c83b0eb3fe8a9084cf71f.png]: /images/20221014/4a64d489fca84350a39219f74ebfcd0f.png
[a54b9f7e54ee4ebbc3d14f2ee4d196fb.png]: /images/20221014/f5cea719c8184157a29435457a68b7d5.png
[Offer 04.]: https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
[bd93575c0908efc3548a1d757720b38c.png]: /images/20221014/df23af493bbb4d84a1376345468516b1.png
[14a4a2ec2b990591c8f725460e04c3ed.png]: /images/20221014/11b25096bca143b0bfda2879cd80a87c.png
[3e4d4154be5fe8d9868259ef6c57dc5e.png]: /images/20221014/b78add1706f1477ab075798a85840738.png
[c8710acc1515262c469ecd56f241c541.png]: /images/20221014/cdf806963efa40c9bf1ea1be5b1c7280.png
[2fac973f6367147085e1d776a1453d02.png]: /images/20221014/388bdc089af84776aaf510c512b77f86.png
[04ddb062aa5c02f6049c8dbe301ffee5.png]: /images/20221014/d4333e59973c4411a7bcf1e841a1d233.png
[7646f4a6cdb192c1a0fbb3491ec03a9c.png]: /images/20221014/ae8a170e77da4bc984951965fcbca91e.png
[451cc5b18903bdf421f83e56c65111a2.png]: /images/20221014/a97a47c28f284a6e99a57fc3753e6d75.png
[827ae36a7e7c172322bb0bf070685904.png]: /images/20221014/eccd773ccdde449e8d17a8abb631055c.png
[3ba5db85b1e2a087cad849bc3d9132f0.png]: /images/20221014/9509e64438414b84a50e35e0b37502f5.png
[c4dc2ceee930c056a87c8778293e74ce.png]: /images/20221014/4c15b963040843b9a2bbf905d6088414.png
[85ccc2607dda22aef618848d15db2b93.png]: /images/20221014/77c767be7fac492b89e4eac0d5f83371.png
[1e8df68365748a72fa28651b0146b164.png]: /images/20221014/82cd2dec0f6348b58a798b1b90fdb88d.png
[60499d2d0cad6532626130fb91c6ce97.png]: /images/20221014/a33d41fa812348f39d4d4f722576ffd7.png
[aca3f14f58674cbbb6fbad175f9e3b05.png]: /images/20221014/cff5df3ab43144b988f1a1ac342aad75.png
[1126d3c72ea3a993482019327b6d14bf.png]: /images/20221014/ba5e0c7f7dfb49cf92363595bc6c292b.png
[79d6c44ea8d6c87ee6665312816d65eb.png]: /images/20221014/d899b6fef72b4fc89278022c698596cb.png
[ac4c67d9ec89c3f0b825aa11119c2ee1.png]: /images/20221014/e6f3aadeade2452eb18d2e0b9af60868.png
[f68f1d6f279d6010b1d925d7a592d495.png]: /images/20221014/346dbd322f884997bde1a067c51020c0.png
[b0a92cf6d191867c6a4a13081e4bf899.png]: /images/20221014/b1a8b9120c0248f68818a9f9aafe32f8.png
[303e5f5e2cd1b19e154ec5de7f78a267.png]: /images/20221014/b043193b3e2d41228dd12e063e859b55.png
[b1eb018bef0ed95a3284d70bfee3adf8.png]: /images/20221014/bc603836e15841708ed50d6db8d58b37.png
[9f06544720aa9008d95ccd6347e2f02e.png]: /images/20221014/6a90ed5d115e4e24828db7e6ab5cb34f.png
[d8db0afc5176180435c192473c9ee6cd.png]: /images/20221014/b5fa63c9658941e3b605e576b18d7b23.png
[240. _ II]: https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
[70.]: https://leetcode-cn.com/problems/climbing-stairs/
[154. _ II]: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
[50. Pow_x_ n]: https://leetcode-cn.com/problems/powx-n/
[37c7fecb1af4ac86a40cc94f02fe04a5.png]: /images/20221014/ee1d731c81784e72aa16a55d7c901e1b.png
[88.]: https://leetcode-cn.com/problems/merge-sorted-array/
[b85b90fb2f833c14e5cffc92b949c247.png]: /images/20221014/62e53800b12e45a6852f740bcdbb3244.png
[861c0ce50c104b2289f35f332f43154d.png]: /images/20221014/fa1f0afcef424cc38f30f53657b1f117.png
[4ff3f2415062bacee7a973afda2270a0.png]: /images/20221014/8449640a83f64363a9aab9a46e8f07c6.png
[2ad2fa95f949f1b78087a212f10ac658.png]: /images/20221014/aa49c9c211984d838808659650329fe2.png