第一题：去除有序数组中的重复元素

题目描述

给定一个排序数组，要求你原地删除重复出现的元素，使得每个元素只出现一次，并返回新的数组长度。注意，要求不使用额外的空间来存储结果，只能修改输入数组。

例如：

• 输入：[0,0,1,1,1,2,2,3,3,4]
• 输出：新数组长度为 5，且数组前 5 个元素为 [0, 1, 2, 3, 4]

题解思路

使用两个指针：

• 慢指针 i：指向当前确定好的不重复元素的最后位置。
• 快指针 j：用于扫描整个数组，查找新的不重复元素。

遍历过程中：

1. 初始时令 i = 0（第一个元素必然是唯一的）。
2. 从 j = 1 开始遍历数组，若 nums[j] 与 nums[i] 不相等，则将 i 加一，并将 nums[j] 赋值到 nums[i] 处。
3. 遍历结束后，i + 1 即为不重复元素的个数。

Python实现

def remove_duplicates(nums):
    if not nums:
        return 0
    i = 0  # 慢指针
    for j in range(1, len(nums)):  # 快指针从1开始
        if nums[j] != nums[i]:
            print(nums[j])
            i += 1  # 找到新元素后，先移动慢指针
            nums[i] = nums[j]  # 更新新位置的值

    return i + 1  # 返回新数组长度

if __name__ == "__main__":
    nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
    length = remove_duplicates(nums)
    print("新数组长度为：", length)
    print("新数组前", length, "个元素为：", nums[:length])

下面逐行解释这个使用双指针思想的代码：

def remove_duplicates(nums):
    if not nums:
        return 0

• 检查空列表
  这两行代码首先判断传入的列表 nums 是否为空。如果为空，则直接返回 0，因为没有元素需要处理。

---

    i = 0  

• 初始化慢指针
  定义变量 i，作为“慢指针”，用于记录当前不重复序列的末尾位置。起始时认为第一个元素总是唯一的，因此将 i 初始化为 0。

---

    for j in range(1, len(nums)):

• 设置快指针
  使用 for 循环遍历列表，j 是“快指针”，从索引 1 开始向后扫描整个列表。这样设计是因为我们已经把第 0 个元素作为唯一序列的起始点了。

---

        if nums[j] != nums[i]:

• 判断是否为新元素
  比较当前快指针指向的元素 nums[j] 与慢指针指向的最后一个不重复元素 nums[i] 是否不同。如果不同，说明找到了一个新的不重复元素。

---

            i += 1  # 找到新元素，移动慢指针
            nums[i] = nums[j]  # 更新慢指针位置的元素

• 更新不重复序列
  • i += 1：将慢指针向前移动一位，为新元素腾出位置。
  • nums[i] = nums[j]：将快指针处的新元素复制到慢指针的新位置。这就保证了从索引 0 到索引 i 的部分都是不重复且按原顺序排列的。

---

    return i + 1  # 新数组长度

• 返回结果
  最后返回 i + 1，因为 i 是最后一个不重复元素的索引，而不重复元素的个数正好是索引加 1。

---

nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
length = remove_duplicates(nums)
print("新数组前", length, "个元素为:", nums[:length])

• 示例说明
  • 输入的列表 [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] 是一个有序数组。
  • 函数会原地修改这个列表，将不重复的元素依次放到前面，并返回不重复元素的个数。
  • 最后使用 nums[:length] 取得新的不重复数组进行输出。

Java 实现

public class RemoveDuplicates {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int i = 0; // 慢指针
        for (int j = 1; j < nums.length; j++) { // 快指针从1开始
            if (nums[j] != nums[i]) {
                i++; // 找到新元素后，先移动慢指针
                nums[i] = nums[j]; // 更新新位置的值
            }
        }
        return i + 1; // 新数组长度为慢指针位置+1
    }

    public static void main(String[] args) {
        int[] nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        RemoveDuplicates solution = new RemoveDuplicates();
        int len = solution.removeDuplicates(nums);
        System.out.println("新数组长度为：" + len);
        System.out.print("新数组前" + len + "个元素为：");
        for (int i = 0; i < len; i++) {
            System.out.print(nums[i] + " ");
        }
    }
}

第二题：两数之和 II - 输入有序数组

题目描述

给定一个 升序排列 的整数数组 numbers 和一个目标值 target，请你在数组中找出两个数，使它们的和等于目标值。返回这两个数字的下标（要求返回的下标从 1 开始计算）。

示例

示例 1：

• 输入： numbers = [2, 7, 11, 15], target = 9
• 输出： [1, 2]
• 解释： 数组中第一个数 2 和第二个数 7 之和为 9。

示例 2：

• 输入： numbers = [2, 3, 4], target = 6
• 输出： [1, 3]
• 解释： 2 + 4 = 6，因此返回下标 1 和 3。

示例 3：

• 输入： numbers = [-1, 0, 1, 2, 4], target = 3
• 输出： [1, 5]
• 解释： -1（数组第 1 个元素）和 4（数组第 5 个元素）的和为 3。

示例 4：

• 输入： numbers = [1, 2, 3, 4, 4, 9, 56, 90], target = 8
• 输出： [4, 5]
• 解释： 数组中第 4 个和第 5 个元素均为 4，它们的和为 8。

示例 5：

• 输入： numbers = [1, 2, 3, 4, 5], target = 10
• 输出： [-1, -1]（或空列表 []）
• 解释： 数组中不存在任何两个数的和等于 10。

解题思路

利用双指针的方法：

1. 初始化指针：设置左指针 left 指向数组开始，右指针 right 指向数组末尾。
2. 计算和：计算两个指针所指元素的和 s
   • 若 s == target，则找到了答案；
   • 若 s < target，说明需要更大的数，左指针右移；
   • 若 s > target，说明需要更小的数，右指针左移。
3. 终止条件：当 left < right 时循环执行，直到找到答案或指针交错。

Python实现

def two_sum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            # 返回的下标从1开始计算
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    # 如果没有找到符合条件的组合，返回空列表
    return []

if __name__ == "__main__":
    numbers = [2, 7, 11, 15]
    target = 9
    result = two_sum(numbers, target)
    print("答案:", result)

Java实现

public class TwoSumII {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                // 下标要求从1开始
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        // 如果没有找到符合条件的组合，返回一个无效下标数组
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        TwoSumII solution = new TwoSumII();
        int[] numbers = {2, 7, 11, 15};
        int target = 9;
        int[] res = solution.twoSum(numbers, target);
        System.out.println("答案: " + res[0] + ", " + res[1]);
    }
}