力扣刷题：数组篇_力扣二维数组中找值,一个很大的二维数组,满足,同一行中从左往右,元素值递增。同一

---

1. 两数之和

题目介绍

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
1
2
3

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
1
2

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]
1
2

提示：

• 2 <= nums.length <= 10³
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• 只会存在一个有效答案

来源：力扣（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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

注意到上一个解法的时间复杂度较高的原因是寻找 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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

11. 盛最多水的容器

题目介绍

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

说明： 你不能倾斜容器。

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

• n = height.length
• 2 <= n <= 3 * 10⁴
• 0 <= height[i] <= 3 * 10⁴

来源：力扣（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;
    }
}
1
2
3
4
5
6
7
8
9
10
11

164. 最大间距

题目介绍

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

示例 1：

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
1
2
3

示例 2：

输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。
1
2
3

说明：

• 你可以假设数组中所有元素都是非负整数，且数值在 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11

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
1
2

示例 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
1
2

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -10⁹ <= matix[i][j] <= 10⁹
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -10⁹ <= target <= 10⁹

相同题目：

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

来源：力扣（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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

26. 删除有序数组中的重复项

题目介绍

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明：

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
1
2
3
4
5
6
7
8

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
1
2
3

示例 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 。不需要考虑数组中超出新长度后面的元素。
1
2
3

提示：

• 0 <= nums.length <= 3 * 10⁴
• -10⁴ <= nums[i] <= 10⁴
• 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

27. 移除元素

题目介绍

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明：

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
1
2
3
4
5
6
7
8

示例 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]，也会被视作正确答案。
1
2
3

示例 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。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
1
2
3

提示：

• 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

75. 颜色分类

题目介绍

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用 整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [0]
输出：[0]
1
2

示例 4：

输入：nums = [1]
输出：[1]
1
2

提示：

• 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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 中的元素。
1
2
3
4

示例 2：

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

示例 3：

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

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -10⁹ <= nums1[i], nums2[j] <= 10⁹

来源：力扣（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);
    }
}
1
2
3
4
5
6
7
8

977. 有序数组的平方

题目介绍

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
     排序后，数组变为 [0,1,9,16,100]
1
2
3
4

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
1
2

提示：

• 1 <= nums.length <= 10⁴
• -10⁴ <= nums[i] <= 10⁴
• 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

剑指 Offer 03. 数组中重复的数字

题目介绍

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 
1
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;
    }
}
1
2
3
4
5
6
7
8
9
10
11

剑指 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]
]
1
2
3
4
5
6
7

给定 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

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

题目实现

如果 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

题目介绍

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

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

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

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

示例 1：

输入：n = 2
输出：1
1
2

示例 2：

输入：n = 5
输出：5
1
2

提示：

• 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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

解法二：变量版

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

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

题目介绍

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

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

示例 1：

输入：n = 2
输出：2
1
2

示例 2：

输入：n = 7
输出：21
1
2

示例 3：

输入：n = 0
输出：1
1
2

提示：

• 0 <= n <= 100

相同题目：

• 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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

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

题目介绍

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

示例 1：

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

示例 2：

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

相同题目：

• 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];
    }
}
1
2
3
4
5
6

解法二：遍历

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11

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

题目介绍

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• -100.0 < x < 100.0
• -2³¹ <= n <= 2³¹-1
• -10⁴ <= xⁿ <= 10⁴

相同题目：

• 50. Pow(x, n)

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

题目实现

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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]
1
2
3
4
5

说明：

• A.length == n + m

相同题目：

• 88. 合并两个有序数组

来源：力扣（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--];
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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]
1
2

提示：

• 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};
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32