额外题目汇总1:数组

数组

1.1365.有多少小于当前数字的数字

力扣题目链接(opens new window)

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

示例 1：

• 输入：nums = [8,1,2,2,3]
• 输出：[4,0,1,1,3]
• 解释： 对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。
  对于 nums[1]=1 不存在比它小的数字。
  对于 nums[2]=2 存在一个比它小的数字：（1）。
  对于 nums[3]=2 存在一个比它小的数字：（1）。
  对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。

示例 2：

• 输入：nums = [6,5,4,8]
• 输出：[2,1,0,3]

示例 3：

• 输入：nums = [7,7,7,7]
• 输出：[0,0,0,0]

提示：

• 2 <= nums.length <= 500
• 0 <= nums[i] <= 100

思路

两层for循环暴力查找，时间复杂度明显为O(n^2)。

首先要找小于当前数字的数字，那么从小到大排序之后，该数字之前的数字就都是比它小的了。

所以可以定义一个新数组，将数组排个序。

排序之后，其实每一个数值的下标就代表这前面有几个比它小的了。

用一个哈希表hash（本题可以就用一个数组）来做数值和下标的映射。这样就可以通过数值快速知道下标（也就是前面有几个比它小的）。

此时有一个情况，就是数值相同怎么办？

例如，数组：1 2 3 4 4 4 ，第一个数值4的下标是3，第二个数值4的下标是4了。

这里就需要一个技巧了，在构造数组hash的时候，从后向前遍历，这样hash里存放的就是相同元素最左面的数值和下标了。 

最后在遍历原数组nums，用hash快速找到每一个数值 对应的 小于这个数值的个数。存放在将结果存放在另一个数组中。

流程如图：

public class How_many_numbers_are_smaller_than_the_current_number {
    public int[] smallerNumbersThanCurrent(int[] nums) {//接受一个整数数组 nums 作为参数，并返回一个整数数组。
        Map<Integer, Integer> map = new HashMap<>(); // 用于记录每个数字有多少个比它小的数字。
        int[] res = Arrays.copyOf(nums, nums.length);//res 是 nums 数组的一个副本，用于排序和后续操作。
        Arrays.sort(res);//对 res 数组进行排序。排序后，数组中的数字按升序排列。
        for (int i = 0; i < res.length; i++) {//遍历排序后的 res 数组。
            if (!map.containsKey(res[i])) { //如果 map 中还没有当前数字 res[i]，则将当前数字和它的索引 i 存入 map。由于数组已经排序，索引 i 就是比 res[i] 小的数字的个数。
                map.put(res[i], i);
            }
        }
        for (int i = 0; i < nums.length; i++) {//遍历原始数组 nums。
            res[i] = map.get(nums[i]);//对于每个数字 nums[i]，从 map 中获取比它小的数字的个数，并存入 res 数组。
        }

        return res;
    }
}

时间复杂度

1. 排序操作： Arrays.sort(res) 的时间复杂度为 O(n log n)，其中 n 是数组 nums 的长度。

2. 遍历操作：遍历排序后的数组 res 和原始数组 nums 各需要 O(n) 的时间。 因此，总的时间复杂度为 O(n log n)。

 空间复杂度

1. 哈希表：使用了一个哈希表 map 来存储每个数字及其对应的较小数字的个数，最坏情况下，哈希表的大小为 O(n)。

2. 结果数组：创建了一个与输入数组相同大小的结果数组 res ，其空间复杂度也是 O(n)。 因此，总的空间复杂度为 O(n)。

综上所述，这段代码的时间复杂度为 O(n log n)，空间复杂度为 O(n)。 

假设输入数组为 nums = [8, 1, 2, 2, 3]，代码的执行过程如下：

1. 排序：res = [1, 2, 2, 3, 8]

2. 填充 map：

   • map = {1: 0, 2: 1, 3: 3, 8: 4}

3. 生成结果数组：

   • res[0] = map.get(8) = 4

   • res[1] = map.get(1) = 0

   • res[2] = map.get(2) = 1

   • res[3] = map.get(2) = 1

   • res[4] = map.get(3) = 3

4. 返回结果：res = [4, 0, 1, 1, 3]

2.941.有效的山脉数组

力扣题目链接(opens new window)

给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。

让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：

• arr.length >= 3
• 在 0 < i < arr.length - 1 条件下，存在 i 使得：
  • arr[0] < arr[1] < ... arr[i-1] < arr[i]
  • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

示例 1：

• 输入：arr = [2,1]
• 输出：false

示例 2：

• 输入：arr = [3,5,5]
• 输出：false

示例 3：

• 输入：arr = [0,3,2,1]
• 输出：true

思路

判断是山峰，主要就是要严格的保存左边到中间，和右边到中间是递增的。

这样可以使用两个指针，left和right，让其按照如下规则移动，如图：

注意这里还是有一些细节，例如如下两点：

• 因为left和right是数组下标，移动的过程中注意不要数组越界
• 如果left或者right没有移动，说明是一个单调递增或者递减的数组，依然不是山峰

系统学双指针， 可以看一下这篇双指针法：总结篇！

public class Valid_Mountain_Array {
    public boolean validMountainArray(int[] arr) {//接收一个整数数组 arr 作为参数，并返回一个布尔值，表示该数组是否为有效的山脉数组。
        if (arr == null || arr.length < 3) { //由于有效的山脉数组至少需要有三个元素（一个上升段、一个峰值和一个下降段），所以如果数组的长度小于 3，直接返回 false。
            return false;
        }
        int left = 0;//双指针法，left 指针初始化为数组的起始位置（索引为 0），right 指针初始化为数组的末尾位置（索引为 arr.length - 1）。
        int right = arr.length - 1;
        while (left + 1 < arr.length && arr[left] < arr[left + 1]) {//使用 while 循环，只要 left + 1 不越界（即 left + 1 < arr.length），并且当前元素 arr[left] 小于下一个元素 arr[left + 1]，就将 left 指针向右移动一位。这一步是为了找到数组上升段的结束位置。
            left++;
        }
        // 检查是否没有上升段
        if (left == 0) {
            return false;
        }
        while (right > 0 && arr[right] < arr[right - 1]) {//使用 while 循环，只要 right 指针不越界（即 right > 0），并且当前元素 arr[right] 小于前一个元素 arr[right - 1]，就将 right 指针向左移动一位。这一步是为了找到数组下降段的起始位置。
            right--;
        }
        // 检查是否没有下降段
        if (right == arr.length - 1) {
            return false;
        }
        // 如果 left 指针和 right 指针最终相遇，并且相遇的位置既不是数组的起始位置也不是数组的末尾位置
        // 说明数组存在一个峰值，且满足上升和下降的条件，返回 true
        return left == right;
    }

}

时间复杂度  

1. 上升段的遍历：第一个 while 循环用于找到数组的上升段。最坏情况下，这个循环会遍历整个数组，时间复杂度为O(n),其中n是数组的长度。

2. 下降段的遍历：  第二个 while 循环用于找到数组的下降段。这个循环同样在最坏情况下也会遍历整个数组，时间复杂度为 O(n)。

因此，整体时间复杂度为： O(n) + O(n) = O(n) 

空间复杂度

1. 使用的额外空间： 该算法只使用了几个整数变量（ left 、 right ），没有使用任何与输入规模成比例的额外数据结构。因此，空间复杂度是常数级别的。因此，整体空间复杂度为： O(1)  

时间复杂度：O(n) 

空间复杂度：O(1)

arr = [1, 3, 5, 4, 2] 时

1. 长度检查

数组 arr = [1, 3, 5, 4, 2] 的长度为 5，不满足 arr == null 或者 arr.length < 3 的条件，所以程序会继续执行后续代码。

2. 初始化双指针

eft 指针初始化为 0，指向数组的第一个元素 1；right 指针初始化为 arr.length - 1 = 4，指向数组的最后一个元素 2。

3. 左指针移动（寻找上升段结束位置）

• 初始时，left = 0，arr[0] = 1，arr[1] = 3，满足 arr[left] < arr[left + 1]，left 指针右移一位，此时 left = 1。
• 接着，arr[1] = 3，arr[2] = 5，满足条件，left 指针再右移一位，此时 left = 2。
• 然后，arr[2] = 5，arr[3] = 4，不满足 arr[left] < arr[left + 1] 条件，左指针移动结束，此时 left = 2。

4. 检查是否没有上升段

由于 left = 2 不等于 0，说明数组存在上升段，程序继续执行后续代码。

5. 右指针移动（寻找下降段起始位置）

• 初始时，right = 4，arr[4] = 2，arr[3] = 4，满足 arr[right] < arr[right - 1]，right 指针左移一位，此时 right = 3。
• 接着，arr[3] = 4，arr[2] = 5，满足条件，right 指针再左移一位，此时 right = 2。
• 然后，arr[2] = 5，arr[1] = 3，不满足 arr[right] < arr[right - 1] 条件，右指针移动结束，此时 right = 2。

6. 检查是否没有下降段

由于 right = 2 不等于 arr.length - 1 = 4，说明数组存在下降段，程序继续执行后续代码。

7. 最终判断

此时 left = 2，right = 2，left == right 条件成立，所以方法返回 true，表明数组 [1, 3, 5, 4, 2] 是一个有效的山脉数组。

3.1207.独一无二的出现次数

力扣题目链接(opens new window)

给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

示例 1：

• 输入：arr = [1,2,2,1,1,3]
• 输出：true
• 解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。

示例 2：

• 输入：arr = [1,2]
• 输出：false

示例 3：

• 输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]
• 输出：true

提示：

• 1 <= arr.length <= 1000
• -1000 <= arr[i] <= 1000

思路

这道题目数组在是哈希法中的经典应用，如果对数组在哈希法中的使用还不熟悉的同学可以看这两篇：数组在哈希法中的应用 (opens new window)和哈希法：383. 赎金信(opens new window)

进而可以学习一下set在哈希法中的应用 (opens new window)，以及map在哈希法中的应用(opens new window)

回归本题，本题强调了-1000 <= arr[i] <= 1000，那么就可以用数组来做哈希，arr[i]作为哈希表（数组）的下标，那么arr[i]可以是负数，怎么办？负数不能做数组下标。

此时可以定义一个2001大小的数组，例如int count[2001];，统计的时候，将arr[i]统一加1000，这样就可以统计arr[i]的出现频率了。

题目中要求的是是否有相同的频率出现，那么需要再定义一个哈希表（数组）用来记录频率是否重复出现过，bool fre[1001]; 定义布尔类型的就可以了，因为题目中强调1 <= arr.length <= 1000，所以哈希表大小为1000就可以了。

如图所示：

public class Unique_number_of_occurrences {
    public boolean uniqueOccurrences(int[] arr) {//公共方法，接收一个整数数组 arr 作为参数，返回一个布尔值，表示数组中元素的出现次数是否独一无二。
        int[] count = new int[2001];//创建一个长度为 2001 的整数数组 count，用于统计数组 arr 中每个元素的出现次数。这里数组长度设为 2001 是为了涵盖可能的整数范围，因为题目中可能会出现负数，通过 j + 1000 的操作将元素值映射到 0 到 2000 的范围内，避免负数作为数组下标。
        for (int j : arr) {//使用增强 for 循环遍历数组 arr 中的每个元素 j。
            count[j + 1000]++; // 防止负数作为下标,将元素 j 对应的计数位置（j + 1000）的值加 1，以此统计元素 j 的出现次数。
        }
        boolean[] flag = new boolean[1002]; // 创建一个长度为 1002 的布尔数组 flag，用于标记每个出现次数是否已经出现过。因为数组 arr 的长度最大为 1000，所以元素的出现次数最大为 1000，加上 0 这种情况，包含 0 到 1000 这 1001 个值，数组长度至少为 1001。不过，代码中为了保险起见，将数组长度设为 1002，多预留了一个位置，虽然从逻辑上来说，1001 的长度已经足够，但 1002 并不会影响功能的实现，还能避免一些潜在的边界问题。
        for (int i = 0; i <= 2000; i++) {//遍历 count 数组，检查每个元素的出现次数。
            if (count[i] > 0) {//如果 count[i] 大于 0，说明元素 i - 1000 在数组 arr 中出现过。
                if (!flag[count[i]]) {//如果 flag[count[i]] 为 false，表示该出现次数还未出现过，将 flag[count[i]] 设为 true，标记该出现次数已经出现过。
                    flag[count[i]] = true;
                } else {//如果 flag[count[i]] 为 true，说明该出现次数已经出现过，即存在元素的出现次数重复，返回 false。
                    return false;
                }
            }
        }
        return true;//如果遍历完 count 数组都没有发现重复的出现次数，说明数组中元素的出现次数是独一无二的，返回 true。
    }
}

时间复杂度

1. 统计出现次数： 第一个循环遍历输入数组 arr ，在 count 数组中更新每个元素的出现次数。这个循环的时间复杂度为 O(n)，其中 n 是输入数组的长度。

2. 检查出现次数是否唯一：  第二个循环遍历 count 数组，检查每个元素的出现次数。这个循环的时间复杂度是 O(1)，因为 count 数组的长度是固定的（2001），无论输入数组的大小如何。 因此，整体时间复杂度为： O(n) + O(1) = O(n) 

空间复杂度

1. 使用的额外空间： count 数组的长度为 2001，用于统计元素的出现次数。 flag 数组的长度为 1002，用于标记每个出现次数是否已经出现过。 这些数组的大小是固定的，与输入数组的大小无关。因此，空间复杂度是常数级别的。 因此，整体空间复杂度为： O(1)  

时间复杂度：O(n) 

空间复杂度：O(1)

 元素出现次数唯一的数组 [1, 2, 2, 1, 1, 3]

1. 统计元素出现次数：
   • 初始化 count 数组，长度为 2001，所有元素初始值为 0。
   • 遍历数组 arr：
     • 遇到元素 1，count[1 + 1000] 即 count[1001] 加 1，此时 count[1001] = 1。
     • 遇到元素 2，count[2 + 1000] 即 count[1002] 加 1，此时 count[1002] = 1。
     • 再次遇到元素 2，count[1002] 再加 1，此时 count[1002] = 2。
     • 再次遇到元素 1，count[1001] 再加 1，此时 count[1001] = 2。
     • 再次遇到元素 1，count[1001] 再加 1，此时 count[1001] = 3。
     • 遇到元素 3，count[3 + 1000] 即 count[1003] 加 1，此时 count[1003] = 1。
   • 最终 count 数组中，count[1001] = 3，count[1002] = 2，count[1003] = 1，其他位置为 0。
2. 检查出现次数是否唯一：
   • 初始化 flag 数组，长度为 1002，所有元素初始值为 false。
   • 遍历 count 数组：
     • 当 i = 1001 时，count[1001] = 3，flag[3] 为 false，将 flag[3] 设为 true。
     • 当 i = 1002 时，count[1002] = 2，flag[2] 为 false，将 flag[2] 设为 true。
     • 当 i = 1003 时，count[1003] = 1，flag[1] 为 false，将 flag[1] 设为 true。
   • 遍历完 count 数组，没有发现重复的出现次数，返回 true。

4.283. 移动零：动态规划：一样的套路，再求一次完全平方数

力扣题目链接(opens new window)

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明:

必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。

思路

可以做一做27.移除元素(opens new window)

这道题目，使用暴力的解法，可以两层for循环，模拟数组删除元素（也就是向前覆盖）的过程。

双指针法总结双指针法：总结篇！ (opens new window)。

双指针法在数组移除元素中，可以达到O(n)的时间复杂度，在27.移除元素 (opens new window)里已经详细讲解了，那么本题和移除元素其实是一个套路。

相当于对整个数组移除元素0，然后slowIndex之后都是移除元素0的冗余元素，把这些元素都赋值为0就可以了。

如动画所示：

public class Move_Zeroes {
    public void moveZeroes(int[] nums) {
        int slow = 0;//slow 是一个指针，初始化为 0。它的作用是标记非零元素应该存放的位置。在遍历数组的过程中，slow 指针会逐步向后移动，用于记录下一个非零元素要放置的索引。
        for (int fast = 0; fast < nums.length; fast++) {//fast 是另一个指针，它从数组的起始位置（索引 0）开始，逐步遍历整个数组。
            if (nums[fast] != 0) {//如果当前fast指针指向的元素是非零元素,将该元素赋值给 slow 指针所指向的位置，即 nums[slow] = nums[fast]。然后 slow 指针向后移动一位，即 slow++。这样做的目的是将非零元素依次存放到数组的前面部分，保持它们的相对顺序。
                nums[slow++] = nums[fast];
            }//如果是零元素，fast 指针继续向后移动，而 slow 指针保持不动，等待下一个非零元素的出现。
        }//当第一个 for 循环结束后，slow 指针之前的位置已经存放了所有的非零元素。
        for (int j = slow; j < nums.length; j++) {//从 slow 指针当前的位置开始，将数组中剩余的位置（即 slow 到数组末尾的所有元素）都赋值为 0。这样就完成了将所有 0 移动到数组末尾的操作。
            nums[j] = 0;
        }
    }

}

时间复杂度

1. 第一个循环（使用 fast 指针）： 这个循环遍历整个数组，时间复杂度为 O(n)，其中 n 是数组的长度。在这个循环中，每个非零元素都会被移动到数组的前面。

2. 第二个循环（填充剩余为零）： -这个循环从 slow 指针的位置一直遍历到数组的末尾，最坏情况下也会遍历整个数组，因此时间复杂度也是 O(n)。 综上所述， moveZeroes 方法的总时间复杂度为： O(n) + O(n) = O(n)  

 空间复杂度 1. 原地修改：该算法直接在输入数组上进行修改，没有使用任何与输入规模成比例的额外数据结构。只使用了几个整数变量（ slow 、 fast 和 j ），这些都是常数空间。 因此， moveZeroes 方法的空间复杂度为： O(1)

时间复杂度：O(n)

空间复杂度：O(1) 

 示例数组 [0, 1, 0, 3, 12]

1. 初始化

• slow = 0
• fast = 0
• 数组 nums = [0, 1, 0, 3, 12]

2. 第一个 for 循环：移动非零元素

• 第一轮迭代（fast = 0）

  • nums[fast] = nums[0] = 0，因为 nums[fast] 为 0，不满足 nums[fast] != 0 的条件，所以 slow 指针不动，fast 指针向后移动一位，此时 fast = 1，slow = 0。

• 第二轮迭代（fast = 1）

  • nums[fast] = nums[1] = 1，满足 nums[fast] != 0 的条件，执行 nums[slow++] = nums[fast]，即 nums[0] = 1，然后 slow 指针向后移动一位，此时 slow = 1，fast = 2，数组变为 [1, 1, 0, 3, 12]。

• 第三轮迭代（fast = 2）

  • nums[fast] = nums[2] = 0，因为 nums[fast] 为 0，不满足 nums[fast] != 0 的条件，所以 slow 指针不动，fast 指针向后移动一位，此时 fast = 3，slow = 1。

• 第四轮迭代（fast = 3）

  • nums[fast] = nums[3] = 3，满足 nums[fast] != 0 的条件，执行 nums[slow++] = nums[fast]，即 nums[1] = 3，然后 slow 指针向后移动一位，此时 slow = 2，fast = 4，数组变为 [1, 3, 0, 3, 12]。

• 第五轮迭代（fast = 4）

  • nums[fast] = nums[4] = 12，满足 nums[fast] != 0 的条件，执行 nums[slow++] = nums[fast]，即 nums[2] = 12，然后 slow 指针向后移动一位，此时 slow = 3，fast = 5，数组变为 [1, 3, 12, 3, 12]。

此时，第一个 for 循环结束，slow 指针之前的位置（索引 0 到 2）存放了所有的非零元素 [1, 3, 12]。

3. 第二个 for 循环：将剩余位置置为 0

• 此时 slow = 3，第二个 for 循环从 j = slow = 3 开始。
  • 当 j = 3 时，nums[j] = nums[3] = 0。
  • 当 j = 4 时，nums[j] = nums[4] = 0。

最终数组变为 [1, 3, 12, 0, 0]，所有的 0 都被移动到了数组的末尾，非零元素的相对顺序保持不变。

5.189. 旋转数组

力扣题目链接(opens new window)

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

进阶：

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

示例 1:

• 输入: nums = [1,2,3,4,5,6,7], k = 3
• 输出: [5,6,7,1,2,3,4]
• 解释: 向右旋转 1 步: [7,1,2,3,4,5,6]。 向右旋转 2 步: [6,7,1,2,3,4,5]。 向右旋转 3 步: [5,6,7,1,2,3,4]。

示例 2:

• 输入：nums = [-1,-100,3,99], k = 2
• 输出：[3,99,-1,-100]
• 解释: 向右旋转 1 步: [99,-1,-100,3]。 向右旋转 2 步: [3,99,-1,-100]。

思路

字符串反转相关的题目：

• 字符串：力扣541.反转字符串II(opens new window)
• 字符串：力扣151.翻转字符串里的单词(opens new window)
• 字符串：剑指Offer58-II.左旋转字符串(opens new window)

本题和字符串：剑指Offer58-II.左旋转字符串 (opens new window)非常像，剑指offer上左旋转，本题是右旋转。

注意题目要求是要求使用空间复杂度为 O(1) 的 原地算法。

在字符串：剑指Offer58-II.左旋转字符串 (opens new window)中，我们提到，如下步骤就可以坐旋转字符串：

1. 反转区间为前n的子串
2. 反转区间为n到末尾的子串
3. 反转整个字符串

本题是右旋转，其实就是反转的顺序改动一下，优先反转整个字符串，步骤如下：

1. 反转整个字符串
2. 反转区间为前k的子串
3. 反转区间为k到末尾的子串

需要注意题目输入中，如果k大于nums.size了应该怎么办？

例如，1,2,3,4,5,6,7 如果右移动15次的话，是 7 1 2 3 4 5 6 。

所以其实就是右移 k % nums.size() 次，即：15 % 7 = 1

public class Rotated_Array {
    private void reverse(int[] nums, int start, int end) {//用于反转数组 nums 中从索引 start 到索引 end 的元素。
        for (int i = start, j = end; i < j; i++, j--) {//使用双指针 i 和 j，分别从起始索引 start 和结束索引 end 开始，向中间移动。在每次循环中，交换 nums[i] 和 nums[j] 的值，直到 i 大于等于 j 为止。
            int temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
        }
    }
    public void rotate(int[] nums, int k) {//将数组 nums 中的元素向右旋转 k 个位置。
        int n = nums.length;//首先获取数组的长度 n，然后对 k 取模 n，这样可以处理 k 大于数组长度的情况。例如，如果数组长度为 7，k 为 10，取模后 k 变为 3，因为旋转 10 个位置和旋转 3 个位置的效果是一样的。
        k %= n;//取模运算符是 %。对于两个整数 a 和 b，a % b 的结果是 a 除以 b 所得的余数。
        reverse(nums, 0, n - 1);//调用 reverse 方法，将整个数组进行反转。例如，对于数组 [1, 2, 3, 4, 5, 6, 7]，反转后变为 [7, 6, 5, 4, 3, 2, 1]。
        reverse(nums, 0, k - 1);//调用 reverse 方法，将数组中从索引 0 到索引 k - 1 的元素进行反转。例如，当 k = 3 时，将 [7, 6, 5] 反转，得到 [5, 6, 7]。此时数组变为 [5, 6, 7, 4, 3, 2, 1]。
        reverse(nums, k, n - 1);//调用 reverse 方法，将数组中从索引 k 到索引 n - 1 的元素进行反转。例如，将 [4, 3, 2, 1] 反转，得到 [1, 2, 3, 4]。此时数组变为 [5, 6, 7, 1, 2, 3, 4]，完成了向右旋转 3 个位置的操作。
    }
}

时间复杂度

反转操作： reverse 方法在每次调用时，最多遍历数组中的所有元素。由于 reverse 方法被调用了三次（分别反转整个数组、反转前 k 个元素和反转后 n-k 个元素），每次调用的时间复杂度都是 O(n)。

空间复杂度

1.反转操作： reverse 方法是就地反转数组，不使用额外的数组或数据结构，因此其空间复杂度为 O(1)。

2.主方法： rotate 方法中没有使用额外的存储空间，除了输入参数和局部变量。 因此，总的空间复杂度为 O(1)。

综上所述，这段代码的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例数组 [1, 2, 3, 4, 5, 6, 7]，k = 3

1. 初始化与取模操作

• n = nums.length = 7
• k %= n，即 k = 3 % 7 = 3

2. 第一次反转：反转整个数组

• 调用 reverse 方法，start = 0，end = 6。
• 初始数组 nums = [1, 2, 3, 4, 5, 6, 7]
• 反转过程：
  • 交换 nums[0] 和 nums[6]，数组变为 [7, 2, 3, 4, 5, 6, 1]
  • 交换 nums[1] 和 nums[5]，数组变为 [7, 6, 3, 4, 5, 2, 1]
  • 交换 nums[2] 和 nums[4]，数组变为 [7, 6, 5, 4, 3, 2, 1]
  • 此时 i = 3，j = 3，循环结束，数组变为 [7, 6, 5, 4, 3, 2, 1]

3. 第二次反转：反转前 k 个元素

• 调用 reverse 方法，start = 0，end = 2。
• 当前数组 nums = [7, 6, 5, 4, 3, 2, 1]
• 反转过程：
  • 交换 nums[0] 和 nums[2]，数组变为 [5, 6, 7, 4, 3, 2, 1]
  • 此时 i = 1，j = 1，循环结束，数组变为 [5, 6, 7, 4, 3, 2, 1]

4. 第三次反转：反转剩余元素

• 调用 reverse 方法，start = 3，end = 6。
• 当前数组 nums = [5, 6, 7, 4, 3, 2, 1]
• 反转过程：
  • 交换 nums[3] 和 nums[6]，数组变为 [5, 6, 7, 1, 3, 2, 4]
  • 交换 nums[4] 和 nums[5]，数组变为 [5, 6, 7, 1, 2, 3, 4]
  • 此时 i = 5，j = 4，循环结束，数组变为 [5, 6, 7, 1, 2, 3, 4]

6.724.寻找数组的中心下标

力扣题目链接(opens new window)

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

示例 1：

• 输入：nums = [1, 7, 3, 6, 5, 6]
• 输出：3
• 解释：中心下标是 3。左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

示例 2：

• 输入：nums = [1, 2, 3]
• 输出：-1
• 解释：数组中不存在满足此条件的中心下标。

示例 3：

• 输入：nums = [2, 1, -1]
• 输出：0
• 解释：中心下标是 0。左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

思路

题目简单直接

1. 遍历一遍求出总和sum
2. 遍历第二遍求中心索引左半和leftSum
   • 同时根据sum和leftSum 计算中心索引右半和rightSum
   • 判断leftSum和rightSum是否相同

public class Find_the_pivot_index_of_an_array {
    public int pivotIndex(int[] nums) {
        int sum = 0;///初始化一个变量 sum 为 0，用于存储数组 nums 中所有元素的总和。
        for (int num : nums) {
            sum += num; //使用 for 循环遍历数组 nums，将每个元素累加到 sum 中。最终，sum 就等于数组中所有元素的总和。
        }
        int leftSum = 0;//用于存储当前下标左侧所有元素的和，初始化为 0。
        int rightSum = 0;///用于存储当前下标右侧所有元素的和，初始化为 0。
        for (int i = 0; i < nums.length; i++) {//使用 for 循环遍历数组 nums，对于每个下标 i
            leftSum += nums[i];//更新左侧元素和：将当前元素 nums[i] 累加到 leftSum 中，这样 leftSum 就表示从数组起始位置到下标 i（包含 i）的所有元素的和。
            rightSum = sum - leftSum + nums[i]; //计算右侧元素和：右侧元素和 rightSum 的计算方式为 sum - leftSum + nums[i]。因为 leftSum 已经包含了当前元素 nums[i]，在 sum - leftSum 时多减去了一次 nums[i]，所以需要再加上 nums[i]，以得到正确的右侧元素和。
            if (leftSum == rightSum) {//如果 leftSum 等于 rightSum，说明找到了中心下标，返回当前下标 i。
                return i;
            }
        }
        return -1; //如果遍历完整个数组都没有找到满足条件的中心下标，则返回 -1，表示数组中不存在中心下标。
    }
}

时间复杂度

1. 计算总和：第一个 for 循环遍历数组 nums ，计算所有元素的总和 sum ，时间复杂度为 O(n)，其中 n 是数组的长度。

2. 寻找中心下标：第二个 for 循环再次遍历数组 nums ，在每次迭代中更新 leftSum 和 rightSum ，时间复杂度也是 O(n)。

因此，总的时间复杂度为 O(n)。

空间复杂度

1. 使用的变量：代码中使用了几个额外的变量（如 sum 、 leftSum 、 rightSum 和循环变量 i ），这些都是常量级别的额外空间，不依赖于输入数组的大小。 因此，总的空间复杂度为 O(1)。

综上所述，这段代码的时间复杂度为 O(n)，空间复杂度为 O(1)。

存在中心下标的数组 [1, 7, 3, 6, 5, 6]

1. 计算数组元素总和：
   • 初始化 sum = 0。
   • 遍历数组 [1, 7, 3, 6, 5, 6]，依次累加元素：sum = 1 + 7 + 3 + 6 + 5 + 6 = 28。
2. 遍历数组寻找中心下标：
   • 当 i = 0 时：
     • leftSum = nums[0] = 1。
     • rightSum = sum - leftSum + nums[0] = 28 - 1 + 1 = 28。
     • 因为 leftSum != rightSum，继续遍历。
   • 当 i = 1 时：
     • leftSum = leftSum + nums[1] = 1 + 7 = 8。
     • rightSum = sum - leftSum + nums[1] = 28 - 8 + 7 = 27。
     • 因为 leftSum != rightSum，继续遍历。
   • 当 i = 2 时：
     • leftSum = leftSum + nums[2] = 8 + 3 = 11。
     • rightSum = sum - leftSum + nums[2] = 28 - 11 + 3 = 20。
     • 因为 leftSum != rightSum，继续遍历。
   • 当 i = 3 时：
     • leftSum = leftSum + nums[3] = 11 + 6 = 17。
     • rightSum = sum - leftSum + nums[3] = 28 - 17 + 6 = 17。
     • 因为 leftSum == rightSum，返回 i = 3。

7.34. 在排序数组中查找元素的第一个和最后一个位置

力扣链接(opens new window)

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：你可以设计并实现时间复杂度为 $O(\log n)$ 的算法解决此问题吗？

示例 1：

• 输入：nums = [5,7,7,8,8,10], target = 8
• 输出：[3,4]

示例 2：

• 输入：nums = [5,7,7,8,8,10], target = 6
• 输出：[-1,-1]

示例 3：

• 输入：nums = [], target = 0
• 输出：[-1,-1]

思路

二分：

• 704.二分查找(opens new window)
• 35.搜索插入位置(opens new window)

寻找target在数组里的左右边界，有如下三种情况：

• 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
• 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
• 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}

采用二分法来去寻找左右边界，为了让代码清晰，分别写两个二分来寻找左边界和右边界。

寻找右边界

先来寻找右边界，至于二分查找，如果看过704.二分查找 (opens new window)就会知道，二分查找中什么时候用while (left <= right)，什么时候用while (left < right)，其实只要清楚循环不变量，很容易区分两种写法。

这里采用while (left <= right)的写法，区间定义为[left, right]，即左闭右闭的区间。

确定好：计算出来的右边界是不包含target的右边界。

寻找左边界

左边界同理。

处理三种情况

左右边界计算完之后，把三种情况以及对应的处理逻辑完整展现出来。

public class Find_First_and_Last_Position_of_Element_in_Sorted_Array {  
public int[] searchRange2(int[] nums, int target) {
        int index = binarySearch(nums, target);//调用 binarySearch 方法查找目标值的任意一个索引，存储在 index 中。
        if (index == -1) {//如果 index == -1，说明目标值不在数组中，直接返回 [-1, -1]。
            return new int[] {-1, -1};
        }
        int left = index;//初始化 left 和 right 为 index，表示目标值的起始和结束位置。
        int right = index;
        while (left - 1 >= 0 && nums[left - 1] == nums[index]) {// //向左扩展：使用 while 循环向左扩展 left 指针，只要 left - 1 >= 0 且 nums[left - 1] == nums[index]，就将 left 减 1。
            left--;
        }
        while (right + 1 < nums.length && nums[right + 1] == nums[index]) {向右扩展：使用 while 循环向右扩展 right 指针，只要 right + 1 < nums.length 且 nums[right + 1] == nums[index]，就将 right 加 1。
            right++;
        }
        return new int[] {left, right};//最终返回 [left, right] 作为目标值的第一个和最后一个位置。
    }
    public int binarySearch(int[] nums, int target) {//使用二分查找算法在数组 nums 中查找目标值 target，并返回目标值的任意一个索引。如果目标值不存在于数组中，则返回 -1。
        int left = 0;//初始化左右指针 left 和 right 分别指向数组的起始和结束位置。
        int right = nums.length - 1;
        while (left <= right) {//进入二分查找循环，只要 left <= right 就继续循环：
            int mid = left + (right - left) / 2;//计算中间位置 mid，使用 left + (right - left) / 2 避免整数溢出。
            if (nums[mid] == target) {//如果 nums[mid] == target，说明找到了目标值，返回 mid。如果 nums[mid] < target，说明目标值在右半部分，更新 left = mid + 1。如果 nums[mid] > target，说明目标值在左半部分，更新 right = mid - 1。循环结束后，如果没有找到目标值，返回 -1。
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

时间复杂度

1. 二分查找： binarySearch 方法使用二分查找算法来查找目标值 target 。二分查找的时间复杂度为 O(log n)，其中 n 是数组 nums 的长度。

2. 扩展左右边界：在 searchRange2 方法中，找到目标值后，向左和向右扩展边界的过程是线性的，最坏情况下可能会遍历整个数组（例如，当目标值在数组的两端时）。因此，扩展的时间复杂度为 O(n)。 因此，总的时间复杂度为 O(n)。

空间复杂度

1. 使用的变量：代码中使用了几个额外的变量（如 index 、 left 、 right 、 mid 、 left 和 right 指针），这些都是常量级别的额外空间，不依赖于输入数组的大小。 因此，总的空间复杂度为 O(1)。

综上所述，这段代码的时间复杂度为 O(n)，空间复杂度为 O(1)。

nums = [1, 2, 2, 2, 3, 4]，目标值 target = 2。

1. binarySearch 方法执行过程

初始化：left = 0，right = 5，target = 2。

第一次循环：

计算中间位置 mid = left + (right - left) / 2 = 0 + (5 - 0) / 2 = 2。

由于 nums[2] = 2，恰好 nums[2] == target，所以直接返回 mid = 2。

2. searchRange2 方法执行过程

• 获取目标值的一个索引：调用 binarySearch 方法得到 index = 2。
• 向左扩展：
  • 初始化 left = 2，right = 2。
  • 进入向左扩展的 while 循环，left - 1 = 1，nums[1] = 2，满足 left - 1 >= 0 且 nums[left - 1] == nums[index]，所以 left 减 1，变为 1。
  • 再次检查，left - 1 = 0，nums[0] = 1，不满足 nums[left - 1] == nums[index]，向左扩展结束。
• 向右扩展：
  • 进入向右扩展的 while 循环，right + 1 = 3，nums[3] = 2，满足 right + 1 < nums.length 且 nums[right + 1] == nums[index]，所以 right 加 1，变为 3。
  • 再次检查，right + 1 = 4，nums[4] = 3，不满足 nums[right + 1] == nums[index]，向右扩展结束。
• 返回结果：最终返回 [left, right] = [1, 3]，即目标值 2 在数组中首次出现的位置是 1，最后一次出现的位置是 3。

nums = [1, 3, 5, 7, 9]，目标值 target = 4。

1. binarySearch 方法执行过程

• 初始化：
  • left = 0，right = 4（数组 [1, 3, 5, 7, 9] 长度为 5，索引范围是 0 到 4），target = 4。
• 第一次循环：
  • 计算中间位置 mid = left + (right - left) / 2 = 0 + (4 - 0) / 2 = 2。
  • 由于 nums[2] = 5，nums[2] > target（即 5 > 4），所以更新 right = mid - 1 = 1。
• 第二次循环：
  • 计算中间位置 mid = left + (right - left) / 2 = 0 + (1 - 0) / 2 = 0。
  • 因为 nums[0] = 1，nums[0] < target（即 1 < 4），所以更新 left = mid + 1 = 1。
• 第三次循环：
  • 计算中间位置 mid = left + (right - left) / 2 = 1 + (1 - 1) / 2 = 1。
  • 又因为 nums[1] = 3，nums[1] < target（即 3 < 4），所以更新 left = mid + 1 = 2。
• 循环结束判断：
  • 此时 left = 2，right = 1，不满足 left <= right 的条件，循环结束。
  • 由于整个循环过程中都没有找到 nums[mid] == target 的情况，所以返回 -1。

2. searchRange2 方法执行过程

• 获取目标值的索引：
  • 调用 binarySearch 方法得到 index = -1。
• 结果判断：
  • 因为 index == -1，直接返回 [-1, -1]，表示目标值 4 不在数组 [1, 3, 5, 7, 9] 中。

综上所述，当数组为 [1, 3, 5, 7, 9]，目标值为 4 时，searchRange2 方法最终返回 [-1, -1]。

 8.922. 按奇偶排序数组II

力扣题目链接(opens new window)

给定一个非负整数数组 nums， nums 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 nums[i] 为奇数时，i 也是奇数；当 nums[i] 为偶数时， i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

示例：

• 输入：[4,2,5,7]
• 输出：[4,5,2,7]
• 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

public class Sort_Array_By_ParityII { 
 public int[] sortArrayByParityII2(int[] nums) {
        int[] result = new int[nums.length];//：创建一个长度与原数组 nums 相同的新数组 result，用于存储重新排列后的元素。
        int even = 0, odd = 1;//初始化两个索引变量，even 用于记录新数组中偶数索引的位置，初始值为 0；odd 用于记录新数组中奇数索引的位置，初始值为 1。
        for (int num : nums) {//使用增强型 for 循环遍历原数组 nums 中的每一个元素 num。
            if (num % 2 == 0) {//判断当前元素 num 是否为偶数。如果 num 除以 2 的余数为 0，则说明 num 是偶数。
                result[even] = num;//将该偶数元素 num 放入新数组 result 中当前 even 所指向的偶数索引位置。
                even += 2;//将 even 索引值增加 2，以便下一个偶数元素可以被放置到下一个偶数索引位置。
            } else {//如果当前元素 num 不是偶数，即 num 是奇数。result[odd] = num;：将该奇数元素 num 放入新数组 result 中当前 odd 所指向的奇数索引位置。odd += 2;：将 odd 索引值增加 2，以便下一个奇数元素可以被放置到下一个奇数索引位置。
                result[odd] = num;
                odd += 2;
            }
        }
        return result;
    }
}

时间复杂度

1. 遍历原数组：使用增强型 for 循环遍历原数组 nums ，时间复杂度为 O(n)，其中 n 是数组的长度。

2. 元素放置：在遍历过程中，对于每个元素，无论是偶数还是奇数，都只进行常量时间的操作（将元素放入新数组和更新索引）。 因此，总的时间复杂度为 O(n)。

空间复杂度

1. 新数组：创建了一个与原数组 nums 长度相同的新数组 result ，这占用了 O(n) 的空间。

2. 使用的变量：除了新数组外，代码中还使用了几个额外的变量（如 even 、 odd 和 num ），这些都是常量级别的额外空间。 因此，总的空间复杂度为 O(n)。

综上所述，这段代码的时间复杂度为 O(n)，空间复杂度为 O(n)。

nums = [4, 2, 5, 7]

1. 初始化

• result 数组被初始化为长度为 4 的数组，初始元素都为 0，即 [0, 0, 0, 0]。
• even 初始值为 0，用于标记 result 数组中偶数索引的位置。
• odd 初始值为 1，用于标记 result 数组中奇数索引的位置。

2. 遍历原数组 nums

第一次循环：num = 4

• 4 % 2 == 0，所以 4 是偶数。
• 将 4 放入 result 数组的 even 索引位置，即 result[0] = 4，此时 result 数组变为 [4, 0, 0, 0]。
• even 增加 2，变为 2。

第二次循环：num = 2

• 2 % 2 == 0，所以 2 是偶数。
• 将 2 放入 result 数组的 even 索引位置，即 result[2] = 2，此时 result 数组变为 [4, 0, 2, 0]。
• even 增加 2，变为 4。

第三次循环：num = 5

• 5 % 2 != 0，所以 5 是奇数。
• 将 5 放入 result 数组的 odd 索引位置，即 result[1] = 5，此时 result 数组变为 [4, 5, 2, 0]。
• odd 增加 2，变为 3。

第四次循环：num = 7

• 7 % 2 != 0，所以 7 是奇数。
• 将 7 放入 result 数组的 odd 索引位置，即 result[3] = 7，此时 result 数组变为 [4, 5, 2, 7]。
• odd 增加 2，变为 5。

3. 返回结果

原数组遍历结束后，result 数组已经按照要求重新排列，最终返回 [4, 5, 2, 7]，该数组中偶数索引位置（0 和 2）的元素是偶数，奇数索引位置（1 和 3）的元素是奇数。

9.搜索插入位置

力扣题目链接(opens new window)

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

• 输入: [1,3,5,6], 5
• 输出: 2

示例 2:

• 输入: [1,3,5,6], 2
• 输出: 1

示例 3:

• 输入: [1,3,5,6], 7
• 输出: 4

示例 4:

• 输入: [1,3,5,6], 0
• 输出: 0

思路

题目要在数组中插入目标值，是四种情况。

• 目标值在数组所有元素之前
• 目标值等于数组中某一个元素
• 目标值插入数组中的位置
• 目标值在数组所有元素之后

暴力解法

二分法

题目的前提是数组是有序数组，是使用二分查找的基础条件。

只要看到面试题里给出的数组是有序数组，都可以想一想是否可以使用二分法。

题目强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的。

二分法的思路，例如在这个数组中，使用二分法寻找元素为5的位置，并返回其下标。

二分查找涉及的很多的边界条件。

例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？

这里弄不清楚主要是因为对区间的定义没有想清楚，这就是不变量。

要在二分查找的过程中，保持不变量，这也就是循环不变量 。

二分法第一种写法

定义 target 是在一个在左闭右闭的区间里，也就是[left, right] 。要写while(left <= right)， 为什么要写right = middle - 1。

二分法第二种写法

定义 target 是在一个在左闭右开的区间里，也就是[left, right) 。

那么二分法的边界处理方式则截然不同。

不变量是[left, right)的区间，要写while (left < right)， 为什么要写right = middle。

总结

写二分法清楚区间定义。确定要查找的区间到底是左闭右开[left, right)，还是左闭又闭[left, right]，这就是不变量。然后在二分查找的循环中，坚持循环不变量的原则。

public class Search_Insert_Position {
 public int searchInsert2(int[] nums, int target) {
        int left = 0;//作为二分查找的左边界，初始化为 0，表示从数组的起始位置开始查找。
        int right = nums.length;//作为二分查找的右边界，初始化为 nums.length，注意这里是数组的长度而非最后一个元素的索引，这是因为目标值可能需要插入到数组的末尾。
        while (left < right) {//只要左边界小于右边界，就持续进行二分查找。
            int middle = left + ((right - left) >> 1);//计算中间位置：int middle = left + ((right - left) >> 1)，这里使用 (right - left) >> 1 来计算中间位置相对于 (right - left) / 2 更加高效，因为位运算的速度通常比除法运算快。同时，使用 left + ((right - left) >> 1) 可以避免 left + right 可能导致的整数溢出问题。
            if (nums[middle] > target) {//意味着目标值 target 可能在左半部分，所以更新右边界 right = middle，将搜索范围缩小到左半部分。
                right = middle;
            } else if (nums[middle] < target) {//表示目标值 target 可能在右半部分，更新左边界 left = middle + 1，把搜索范围缩小到右半部分。
                left = middle + 1;
            } else {//说明已经找到了目标值，直接返回中间位置的索引 middle。
                return middle;
            }
        }
        return right;//当 left >= right 时，二分查找结束。此时 right 所指向的位置就是目标值 target 应该插入的位置，所以返回 right。这是因为在二分查找过程中，right 始终指向第一个大于等于目标值的元素的位置。
    }
}

时间复杂度

1. 二分查找：该算法使用了二分查找来查找目标值 target 。每次迭代都会将搜索范围缩小一半，因此时间复杂度为 O(log n)，其中 n 是数组 nums 的长度。

空间复杂度

1. 使用的变量：代码中使用了几个额外的变量（如 left 、 right 和 middle ），这些都是常量级别的额外空间，不依赖于输入数组的大小。 因此，总的空间复杂度为 O(1)。

综上所述，这段代码的时间复杂度为 O(log n)，空间复杂度为 O(1)。

示例 1：目标值存在于数组中

假设数组 nums = [1, 3, 5, 6]，目标值 target = 5。

执行步骤

1. 初始化：
   • left = 0，right = 4（数组长度）。
2. 第一次循环：
   • 计算中间位置 middle = left + ((right - left) >> 1) = 0 + ((4 - 0) >> 1) = 2。
   • 此时 nums[middle] = nums[2] = 5，恰好 nums[middle] == target，所以直接返回 middle = 2。

示例 2：目标值不存在于数组中，需要插入到数组中间

假设数组 nums = [1, 3, 5, 6]，目标值 target = 2。

执行步骤

1. 初始化：
   • left = 0，right = 4。
2. 第一次循环：
   • 计算中间位置 middle = left + ((right - left) >> 1) = 0 + ((4 - 0) >> 1) = 2。
   • nums[middle] = nums[2] = 5，因为 nums[middle] > target（即 5 > 2），所以更新 right = middle = 2。
3. 第二次循环：
   • 计算中间位置 middle = left + ((right - left) >> 1) = 0 + ((2 - 0) >> 1) = 1。
   • nums[middle] = nums[1] = 3，由于 nums[middle] > target（即 3 > 2），所以更新 right = middle = 1。
4. 第三次循环：
   • 计算中间位置 middle = left + ((right - left) >> 1) = 0 + ((1 - 0) >> 1) = 0。
   • nums[middle] = nums[0] = 1，因为 nums[middle] < target（即 1 < 2），所以更新 left = middle + 1 = 1。
5. 循环结束判断：
   • 此时 left = 1，right = 1，不满足 left < right 的条件，循环结束。
   • 返回 right = 1，即目标值 2 应该插入到数组的索引为 1 的位置，插入后数组变为 [1, 2, 3, 5, 6]。

示例 3：目标值不存在于数组中，需要插入到数组开头

假设数组 nums = [1, 3, 5, 6]，目标值 target = 0。

执行步骤

1. 初始化：
   • left = 0，right = 4。
2. 第一次循环：
   • 计算中间位置 middle = left + ((right - left) >> 1) = 0 + ((4 - 0) >> 1) = 2。
   • nums[middle] = nums[2] = 5，因为 nums[middle] > target（即 5 > 0），所以更新 right = middle = 2。
3. 第二次循环：
   • 计算中间位置 middle = left + ((right - left) >> 1) = 0 + ((2 - 0) >> 1) = 1。
   • nums[middle] = nums[1] = 3，由于 nums[middle] > target（即 3 > 0），所以更新 right = middle = 1。
4. 第三次循环：
   • 计算中间位置 middle = left + ((right - left) >> 1) = 0 + ((1 - 0) >> 1) = 0。
   • nums[middle] = nums[0] = 1，因为 nums[middle] > target（即 1 > 0），所以更新 right = middle = 0。
5. 循环结束判断：
   • 此时 left = 0，right = 0，不满足 left < right 的条件，循环结束。
   • 返回 right = 0，即目标值 0 应该插入到数组的索引为 0 的位置，插入后数组变为 [0, 1, 3, 5, 6]。

示例 4：目标值不存在于数组中，需要插入到数组末尾

假设数组 nums = [1, 3, 5, 6]，目标值 target = 7。

执行步骤

1. 初始化：
   • left = 0，right = 4。
2. 第一次循环：
   • 计算中间位置 middle = left + ((right - left) >> 1) = 0 + ((4 - 0) >> 1) = 2。
   • nums[middle] = nums[2] = 5，因为 nums[middle] < target（即 5 < 7），所以更新 left = middle + 1 = 3。
3. 第二次循环：
   • 计算中间位置 middle = left + ((right - left) >> 1) = 3 + ((4 - 3) >> 1) = 3。
   • nums[middle] = nums[3] = 6，由于 nums[middle] < target（即 6 < 7），所以更新 left = middle + 1 = 4。
4. 循环结束判断：
   • 此时 left = 4，right = 4，不满足 left < right 的条件，循环结束。
   • 返回 right = 4，即目标值 7 应该插入到数组的索引为 4 的位置，插入后数组变为 [1, 3, 5, 6, 7]。