day 1 任务以及具体安排：第一章 数组part01

第一题：704. 二分查找 - 力扣（LeetCode）

解题思路

本题要求在一个升序排列且无重复元素的整型数组 中查找目标值 target，并返回其下标。若不存在则返回 -1。由于数组有序且无重复元素，二分查找 是最优解法。

二分查找核心思想

1. 区间定义 ：本题使用左闭右闭区间 [left, right]，即初始 left = 0，right = nums.length - 1。
2. 循环条件为 left <= right，确保所有可能区间都被覆盖（包括只剩一个元素的情况）
3. 中间值计算 ：通过 middle = (left + right) >> 1 计算中间索引（位运算优化），避免整数溢出问题（本题数据量较小无需额外处理）
4. 区间调整 ：
   • 若 nums[middle] > target，说明目标在左半区间，调整 right = middle - 1。
   • 若 nums[middle] < target，说明目标在右半区间，调整 left = middle + 1。
   • 若相等，直接返回 middle

代码：

class Solution {
    public int search(int[] nums, int target) {
        // 初始化左右指针，定义搜索区间 [left, right]
        int left = 0;
        int right = nums.length - 1;

        // 循环条件：确保所有可能区间都被覆盖（包括 left == right 的情况）
        while (left <= right) {
            // 计算中间索引，使用位运算代替除法，避免整数溢出风险（本题无需特殊处理）
            int middle = (left + right) >> 1;

            // 情况 1：中间值大于目标值，说明目标在左半区间
            if (nums[middle] > target) {
                right = middle - 1;
            } 
            // 情况 2：中间值小于目标值，说明目标在右半区间
            else if (nums[middle] < target) {
                left = middle + 1;
            } 
            // 情况 3：找到目标值，返回下标
            else {
                return middle;
            }
        }

        // 循环结束仍未找到目标值，返回 -1
        return -1;
    }
}

 第二题：27. 移除元素 - 力扣（LeetCode）

解题思路

本题要求原地 移除数组中所有等于 val 的元素，并返回新的长度 k，同时确保数组的前 k 个元素为不等于 val 的元素。题目允许元素顺序改变，且不允许使用额外空间。因此，双指针法 是最优解。

双指针法的核心思想：

1. 快指针（fast） ：用于遍历数组，寻找不等于 val 的元素。
2. 慢指针（slow） ：指向下一个可以放置有效元素（不等于 val）的位置。
3. 当快指针找到不等于 val 的元素时，将其值赋给慢指针所在位置，并移动慢指针。

通过这种方式，所有不等于 val 的元素会被依次移动到数组的前 k 个位置，且时间复杂度为 O(n)，空间复杂度为 O(1)。

代码：

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0; // 慢指针，指向下一个有效元素的位置
        for (int fast = 0; fast < nums.length; fast++) { // 快指针遍历数组
            if (nums[fast] != val) { // 找到不等于 val 的元素
                nums[slow] = nums[fast]; // 将有效元素移动到 slow 位置
                slow++; // 慢指针后移
            }
        }
        return slow; // 最终 slow 即为新长度 k
    }
}

第三题：977. 有序数组的平方 - 力扣（LeetCode）

解题思路

题目要求对一个非递减排序的整数数组 nums，返回其每个元素的平方，并保持平方后的数组也是非递减排序 的。

关键观察

• 原数组是非递减排序 的，即 nums[0] <= nums[1] <= ... <= nums[n-1]。
• 由于负数的存在，平方后的最大值可能出现在数组的两端（例如 -4 和 10 的平方分别是 16 和 100）。
• 因此，平方后的最大值一定出现在数组的最左端或最右端 ，最小值则在中间。

双指针法核心思想

1. 使用两个指针 left 和 right，分别指向数组的最左端 和最右端 。
2. 使用一个指针 index，从结果数组的末尾 开始填充（从后往前填），确保每次填入的是当前最大的平方值。
3. 比较 nums[left] 和 nums[right] 的平方：
   • 如果 nums[left]^2 > nums[right]^2，说明左边的平方更大，将其放入 result[index]，并移动 left++。
   • 否则，右边的平方更大，将其放入 result[index]，并移动 right--。
4. 每次操作后，index--，直到 left > right 为止。

这种方法的时间复杂度为 O(n)，空间复杂度为 O(n)（因为需要一个额外的结果数组）。

代码：

class Solution {
    public int[] sortedSquares(int[] nums) {
        // 初始化左右指针
        int left = 0;
        int right = nums.length - 1;

        // 创建结果数组，用于存储平方后的元素
        int[] result = new int[nums.length];

        // 结果数组的填充索引，从后往前填充
        int index = result.length - 1;

        // 双指针遍历数组
        while (left <= right) {
            // 计算左右指针对应元素的平方
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];

            // 比较平方值，较大的那个放入结果数组的当前索引位置
            if (leftSquare > rightSquare) {
                result[index--] = leftSquare;
                left++; // 左指针右移
            } else {
                result[index--] = rightSquare;
                right--; // 右指针左移
            }
        }

        // 返回最终的平方数组
        return result;
    }
}