167.两数之和II-输入有序数组

LeetCode LeetCode 数组双指针二分查找

发布时间 : 2000-01-10 01:06

字数:1.6k 阅读 :

167.两数之和II-输入有序数组

167.两数之和II-输入有序数组

167.1 题目

给你一个下标从 1 开始的整数数组 numbers，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2]，则 1 <= index1 < index2 <= numbers.length。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9。因此 index1 = 1, index2 = 2。返回 [1, 2]。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6。因此 index1 = 1, index2 = 3。返回 [1, 3]。

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1。因此 index1 = 1, index2 = 2。返回 [1, 2]。

提示：

2 <= numbers.length <= 3 * 10^4
-1000 <= numbers[i] <= 1000
numbers 按非递减顺序排列
-1000 <= target <= 1000
仅存在一个有效答案

167.2 题解

双指针法

// 方法一：双指针法
// 头尾移动判断是否是目标值
static int[] TwoSum1(int[] numbers, int target)
{
    // 初始化左右指针
    int left = 0;
    int right = numbers.Length - 1;

    // 循环直到左指针大于右指针
    while (left < right)
    {
        // 计算当前左右指针指向的数字之和
        int sum = numbers[left] + numbers[right];
        // 如果和等于目标数，返回左右指针的下标
        if (sum == target)
        {
            return new int[] { left + 1, right + 1 };
        }
        // 如果和小于目标数，左指针右移一位
        else if (sum < target)
        {
            left++;
        }
        // 如果和大于目标数，右指针左移一位
        else
        {
            right--;
        }
    }

    // 没有找到符合条件的数对，返回[-1, -1]
    return new int[] { -1, -1 };
}

字典存储补数

// 方法二：字典存储补数
static int[] TwoSum2(int[] numbers, int target)
{
    // 创建哈希表，存储数字及其下标
    var dict = new Dictionary<int, int>();

    // 遍历数组
    for (int i = 0; i < numbers.Length; i++)
    {
        // 计算当前数字的补数
        int complement = target - numbers[i];
        // 如果补数在哈希表中存在，则返回其下标及当前数字的下标
        if (dict.ContainsKey(complement))
        {
            return new int[] { dict[complement] + 1, i + 1 };
        }

        // 将当前数字及其下标存入哈希表
        dict[numbers[i]] = i;
    }

    // 没有找到符合条件的数对，返回[-1, -1]
    return new int[] { -1, -1 };
}

167.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。
        // 如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
        // 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
        // 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
        // 你所设计的解决方案必须只使用常量级的额外空间。

        // 示例 1：
        // 输入：numbers = [2,7,11,15], target = 9
        // 输出：[1,2]
        // 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

        // 示例 2：
        // 输入：numbers = [2,3,4], target = 6
        // 输出：[1,3]
        // 解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

        // 示例 3：
        // 输入：numbers = [-1,0], target = -1
        // 输出：[1,2]
        // 解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

        // 提示：
        // 2 <= numbers.length <= 3 * 104
        // -1000 <= numbers[i] <= 1000
        // numbers 按 非递减顺序 排列
        // -1000 <= target <= 1000
        // 仅存在一个有效答案

        #endregion

        #region 测试

        // 示例 1
        int[] numbers1 = { 2, 7, 11, 15 };
        int target1 = 9;
        int[] result1_1 = TwoSum1(numbers1, target1);
        Console.WriteLine($"示例1 方法1 输出：[{result1_1[0]}, {result1_1[1]}]");
        int[] result1_2 = TwoSum2(numbers1, target1);
        Console.WriteLine($"示例1 方法2 输出：[{result1_2[0]}, {result1_2[1]}]");

        // 示例 2
        int[] numbers2 = { 2, 3, 4 };
        int target2 = 6;
        int[] result2_1 = TwoSum1(numbers2, target2);
        Console.WriteLine($"示例2 方法1 输出：[{result2_1[0]}, {result2_1[1]}]");
        int[] result2_2 = TwoSum2(numbers2, target2);
        Console.WriteLine($"示例2 方法2 输出：[{result2_2[0]}, {result2_2[1]}]");

        // 示例 3
        int[] numbers3 = { -1, 0 };
        int target3 = -1;
        int[] result3_1 = TwoSum1(numbers3, target3);
        Console.WriteLine($"示例3 方法1 输出：[{result3_1[0]}, {result3_1[1]}]");
        int[] result3_2 = TwoSum2(numbers3, target3);
        Console.WriteLine($"示例3 方法2 输出：[{result3_2[0]}, {result3_2[1]}]");

        #endregion
    }

    #region 答案

    // 方法一：双指针法
    // 头尾移动判断是否是目标值
    static int[] TwoSum1(int[] numbers, int target)
    {
        // 初始化左右指针
        int left = 0;
        int right = numbers.Length - 1;

        // 循环直到左指针大于右指针
        while (left < right)
        {
            // 计算当前左右指针指向的数字之和
            int sum = numbers[left] + numbers[right];
            // 如果和等于目标数，返回左右指针的下标
            if (sum == target)
            {
                return new int[] { left + 1, right + 1 };
            }
            // 如果和小于目标数，左指针右移一位
            else if (sum < target)
            {
                left++;
            }
            // 如果和大于目标数，右指针左移一位
            else
            {
                right--;
            }
        }

        // 没有找到符合条件的数对，返回[-1, -1]
        return new int[] { -1, -1 };
    }

    // 方法二：字典存储补数
    static int[] TwoSum2(int[] numbers, int target)
    {
        // 创建哈希表，存储数字及其下标
        var dict = new Dictionary<int, int>();

        // 遍历数组
        for (int i = 0; i < numbers.Length; i++)
        {
            // 计算当前数字的补数
            int complement = target - numbers[i];
            // 如果补数在哈希表中存在，则返回其下标及当前数字的下标
            if (dict.ContainsKey(complement))
            {
                return new int[] { dict[complement] + 1, i + 1 };
            }

            // 将当前数字及其下标存入哈希表
            dict[numbers[i]] = i;
        }

        // 没有找到符合条件的数对，返回[-1, -1]
        return new int[] { -1, -1 };
    }

    #endregion
}

167.4 运行结果

示例1 方法1 输出：[1, 2]
示例1 方法2 输出：[1, 2]
示例2 方法1 输出：[1, 3]
示例2 方法2 输出：[1, 3]
示例3 方法1 输出：[1, 2]
示例3 方法2 输出：[1, 2]

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com