力扣面试经典——167题

💡 参考代码：

/**
 * 两数之和 II - 输入有序数组
 * 
 * 给定一个按非递减顺序排列的整数数组，找出两个数使得它们的和等于目标值
 * 返回这两个数的下标（下标从1开始）
 * 
 * 解题思路：
 * 使用双指针法，利用数组有序的特性
 * 设置左指针指向数组开始，右指针指向数组结束
 * 根据当前两数之和与目标值的比较，移动指针
 * 
 * 时间复杂度：O(n) - 最多遍历一次数组
 * 空间复杂度：O(1) - 只使用常量级额外空间
 * 
 * @param numbers 输入的有序整数数组
 * @param numbersSize 数组长度
 * @param target 目标和
 * @param returnSize 返回数组的长度
 * @return 包含两个下标的数组
 */
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
    // 分配返回数组内存
    int* result = (int*)malloc(2 * sizeof(int));
    *returnSize = 2;
    
    // 初始化双指针
    int left = 0;          // 左指针，指向数组开始
    int right = numbersSize - 1;  // 右指针，指向数组结束
    
    // 双指针向中间移动查找
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        
        if (sum == target) {
            // 找到目标和，注意题目要求下标从1开始
            result[0] = left + 1;
            result[1] = right + 1;
            return result;
        } else if (sum < target) {
            // 当前和小于目标值，左指针右移增大和值
            left++;
        } else {
            // 当前和大于目标值，右指针左移减小和值
            right--;
        }
    }
    
    // 根据题目保证有唯一解，此处不会执行到
    return result;
}

📖 总结：

点击展开题目总结

🤔 两数之和Ⅱ-输入有序数组

---

1️⃣ 题目核心信息

🎯 功能描述：在一个非递减有序整数数组中找到两个数，使其和等于目标值，并返回这两个数的下标（从1开始）

📥 输入输出：

• 输入：
  • numbers: 按非递减顺序排列的整数数组
  • target: 目标和值
• 输出：包含两个下标的数组 [index1, index2]，其中 1 <= index1 < index2 <= numbers.length

---

2️⃣ 实现原理

💡 核心思路：利用数组有序的特性，使用双指针技术从两端向中间搜索，根据当前和与目标值的比较来移动指针

📋 实现步骤：

1. 初始化左指针指向数组开始，右指针指向数组结束
2. 计算左右指针所指向元素的和
3. 比较当前和与目标值：
   • 如果相等，则找到答案，返回下标（注意转换为从1开始）
   • 如果小于目标值，左指针右移以增大和值
   • 如果大于目标值，右指针左移以减小和值
4. 重复步骤2-3直到找到答案

---

3️⃣ 关键点解析

🎯 代码技巧

• 双指针法：利用有序数组的特性，避免了O(n²)的暴力搜索
• 有序数组的单调性：根据和值与目标值的比较，可以确定移动哪个指针
• 下标转换：题目要求下标从1开始，需要将数组索引+1

4️⃣ 使用场景

✅ 适用情况：

• 在有序数组中查找满足某种条件的两个元素
• 需要常量级空间复杂度的两数查找问题
• 已知数组有序且有唯一解的情况

⚠️ 前提条件：

• 数组必须是非递减有序排列
• 保证存在唯一解
• 不允许重复使用相同元素

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(n)，其中n是数组长度，最多需要遍历一次数组
• 💾 空间复杂度：O(1)，只使用了常量级额外空间（不计算返回数组）

6️⃣ 注意事项

🚩 边界情况：

• 数组只有两个元素且满足条件
• 目标值由数组首尾元素组成
• 负数参与计算的情况

💥 易错点：

• 忘记将数组索引转换为从1开始的下标
• 指针移动条件判断错误
• 没有正确处理循环终止条件

加载评论中...