1.两数之和

LeetCode LeetCode 数组 哈希表
发布时间 :
字数:2.7k 阅读 : 评论:
  1. 1.两数之和
    1. 1.1 题目
    2. 1.2 题解
      1. 暴力法
      2. 两遍哈希表
      3. 一遍哈希表
    3. 1.3 代码
    4. 1.4 运行结果

1.两数之和

1.1 题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例：

  • 示例 1：

    • 输入：nums = [2,7,11,15], target = 9
    • 输出：[0,1]
    • 解释：因为 nums[0] + nums[1] == 9，返回 [0, 1]。

  • 示例 2：

    • 输入：nums = [3,2,4], target = 6
    • 输出：[1,2]

  • 示例 3：

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

提示：

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • 只会存在一个有效答案

进阶：

你可以想出一个时间复杂度小于 O(n^2) 的算法吗？

1.2 题解

暴力法

//方法一：暴力法
//使用两层循环遍历数组中的每一对数字组合，检查相加是否等于目标值。如果找到符合条件的数字，返回它们的索引数组。
static int[] TwoSum1(int[] nums, int target)
{
    // 使用两层循环遍历数组中的每一对数字组合
    for (int i = 0; i < nums.Length; i++)
    {
        for (int j = i + 1; j < nums.Length; j++)
        {
            // 检查当前两个数字的和是否等于目标值
            if (nums[i] + nums[j] == target)
            {
                // 如果找到符合条件的数字，返回它们的索引数组
                return new int[] { i, j };
            }
        }
    }

    // 如果未找到符合条件的数字组合，返回一个包含两个零的数组
    return new int[] { 0, 0 };
}

两遍哈希表

// 方法二：两遍哈希表
// 第一遍循环：将数组元素及其索引添加到字典中。如果发现相同值的元素，判断值乘2是否等于目标值。
// 第二遍循环：查找目标值与当前元素的差值是否在字典中，确保索引不同。
static int[] TwoSum2(int[] nums, int target)
{
    // 创建一个字典，用于存储数组元素的值和其对应的索引
    Dictionary<int, int> valueAndIndexDictionary = new Dictionary<int, int>();

    // 第一遍循环：将数组元素及其索引添加到字典中
    for (int i = 0; i < nums.Length; i++)
    {
        // 需要对重复值进行判断
        // 如果字典中已经存在相同的值，且该值的两倍等于目标值，直接返回包含这两个索引的数组
        if (valueAndIndexDictionary.ContainsKey(nums[i]))
        {
            if (nums[i] * 2 == target)
            {
                return new int[] { i, valueAndIndexDictionary[nums[i]] };
            }
        }
        // 如果字典中不存在当前值，则将值和索引添加到字典中
        else
        {
            valueAndIndexDictionary.Add(nums[i], i);
        }
    }

    // 第二遍循环：查找目标值与当前元素的差值是否在字典中，并且确保索引不同
    for (int i = 0; i < nums.Length; i++)
    {
        // 计算目标和元素值的差值
        int distance = target - nums[i];

        // 如果字典里有差值的键且改差值键的值不是当前索引，说明有元素的值和当前索引元素值加起来等于目标值
        if (valueAndIndexDictionary.ContainsKey(distance) && valueAndIndexDictionary[distance] != i)
        {
            // 如果找到符合条件的数字组合，返回包含这两个索引的数组
            return new int[] { i, valueAndIndexDictionary[distance] };
        }
    }

    // 如果未找到符合条件的数字组合，返回一个包含两个零的数组
    return new int[] { 0, 0 };
}

一遍哈希表

//方法三：一遍哈希表
//遍历数组时判断哈希表有没有需要的差值，没有就存储数组元素的值和索引到字典。注意重复值判断。
static int[] TwoSum3(int[] nums, int target)
{
    // 创建一个字典，用于存储数组元素的值和其对应的索引
    Dictionary<int, int> valueAndIndexDictionary = new Dictionary<int, int>();

    for (int i = 0; i < nums.Length; i++)
    {
        // 计算目标和元素值的差值
        int distance = target - nums[i];

        // 如果字典里有差值的键且改差值键的值不是当前索引，说明有元素的值和当前索引元素值加起来等于目标值
        if (valueAndIndexDictionary.ContainsKey(distance) && valueAndIndexDictionary[distance] != i)
        {
            // 如果找到符合条件的数字组合，返回包含这两个索引的数组
            return new int[] { i, valueAndIndexDictionary[distance] };
        }

        // 需要对重复值进行判断，若结果包含了重复值，则已经被上面给return了；所以此处对于重复值直接忽略
        if (!valueAndIndexDictionary.ContainsKey(nums[i]))
        {
            valueAndIndexDictionary.Add(nums[i], i);
        }
    }

    // 如果未找到符合条件的数字组合，返回一个包含两个零的数组
    return new int[] { 0, 0 };
}

1.3 代码

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

        // 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
        // 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
        // 你可以按任意顺序返回答案。

        // 示例 1：
        // 输入：nums = [2,7,11,15], target = 9
        // 输出：[0,1]
        // 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]。

        // 示例 2：
        // 输入：nums = [3,2,4], target = 6
        // 输出：[1,2]

        // 示例 3：
        // 输入：nums = [3,3], target = 6
        // 输出：[0,1]

        // 提示：
        // 2 <= nums.length <= 104
        // -109 <= nums[i] <= 109
        // -109 <= target <= 109
        // 只会存在一个有效答案

        // 进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { 2, 7, 11, 15 };
        int target1 = 9;
        int[] result11 = TwoSum1(nums1, target1);
        int[] result12 = TwoSum2(nums1, target1);
        int[] result13 = TwoSum3(nums1, target1);
        Console.WriteLine($"示例1 方法1 输出：[{result11[0]}, {result11[1]}]");
        Console.WriteLine($"示例1 方法2 输出：[{result11[0]}, {result11[1]}]");
        Console.WriteLine($"示例1 方法3 输出：[{result11[0]}, {result11[1]}]");

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

        // 示例 3
        int[] nums3 = { 3, 3 };
        int target3 = 6;
        int[] result31 = TwoSum1(nums3, target3);
        int[] result32 = TwoSum2(nums3, target3);
        int[] result33 = TwoSum3(nums3, target3);
        Console.WriteLine($"示例3 方法1 输出：[{result31[0]}, {result31[1]}]");
        Console.WriteLine($"示例3 方法2 输出：[{result32[0]}, {result32[1]}]");
        Console.WriteLine($"示例3 方法3 输出：[{result33[0]}, {result33[1]}]");

        #endregion
    }

    #region 答案

    //方法一：暴力法
    //使用两层循环遍历数组中的每一对数字组合，检查相加是否等于目标值。如果找到符合条件的数字，返回它们的索引数组。
    static int[] TwoSum1(int[] nums, int target)
    {
        // 使用两层循环遍历数组中的每一对数字组合
        for (int i = 0; i < nums.Length; i++)
        {
            for (int j = i + 1; j < nums.Length; j++)
            {
                // 检查当前两个数字的和是否等于目标值
                if (nums[i] + nums[j] == target)
                {
                    // 如果找到符合条件的数字，返回它们的索引数组
                    return new int[] { i, j };
                }
            }
        }

        // 如果未找到符合条件的数字组合，返回一个包含两个零的数组
        return new int[] { 0, 0 };
    }

    // 方法二：两遍哈希表
    // 第一遍循环：将数组元素及其索引添加到字典中。如果发现相同值的元素，判断值乘2是否等于目标值。
    // 第二遍循环：查找目标值与当前元素的差值是否在字典中，确保索引不同。
    static int[] TwoSum2(int[] nums, int target)
    {
        // 创建一个字典，用于存储数组元素的值和其对应的索引
        Dictionary<int, int> valueAndIndexDictionary = new Dictionary<int, int>();

        // 第一遍循环：将数组元素及其索引添加到字典中
        for (int i = 0; i < nums.Length; i++)
        {
            // 需要对重复值进行判断
            // 如果字典中已经存在相同的值，且该值的两倍等于目标值，直接返回包含这两个索引的数组
            if (valueAndIndexDictionary.ContainsKey(nums[i]))
            {
                if (nums[i] * 2 == target)
                {
                    return new int[] { i, valueAndIndexDictionary[nums[i]] };
                }
            }
            // 如果字典中不存在当前值，则将值和索引添加到字典中
            else
            {
                valueAndIndexDictionary.Add(nums[i], i);
            }
        }

        // 第二遍循环：查找目标值与当前元素的差值是否在字典中，并且确保索引不同
        for (int i = 0; i < nums.Length; i++)
        {
            // 计算目标和元素值的差值
            int distance = target - nums[i];

            // 如果字典里有差值的键且改差值键的值不是当前索引，说明有元素的值和当前索引元素值加起来等于目标值
            if (valueAndIndexDictionary.ContainsKey(distance) && valueAndIndexDictionary[distance] != i)
            {
                // 如果找到符合条件的数字组合，返回包含这两个索引的数组
                return new int[] { i, valueAndIndexDictionary[distance] };
            }
        }

        // 如果未找到符合条件的数字组合，返回一个包含两个零的数组
        return new int[] { 0, 0 };
    }

    //方法三：一遍哈希表
    //遍历数组时判断哈希表有没有需要的差值，没有就存储数组元素的值和索引到字典。注意重复值判断。
    static int[] TwoSum3(int[] nums, int target)
    {
        // 创建一个字典，用于存储数组元素的值和其对应的索引
        Dictionary<int, int> valueAndIndexDictionary = new Dictionary<int, int>();

        for (int i = 0; i < nums.Length; i++)
        {
            // 计算目标和元素值的差值
            int distance = target - nums[i];

            // 如果字典里有差值的键且改差值键的值不是当前索引，说明有元素的值和当前索引元素值加起来等于目标值
            if (valueAndIndexDictionary.ContainsKey(distance) && valueAndIndexDictionary[distance] != i)
            {
                // 如果找到符合条件的数字组合，返回包含这两个索引的数组
                return new int[] { i, valueAndIndexDictionary[distance] };
            }

            // 需要对重复值进行判断，若结果包含了重复值，则已经被上面给return了；所以此处对于重复值直接忽略
            if (!valueAndIndexDictionary.ContainsKey(nums[i]))
            {
                valueAndIndexDictionary.Add(nums[i], i);
            }
        }

        // 如果未找到符合条件的数字组合，返回一个包含两个零的数组
        return new int[] { 0, 0 };
    }

    #endregion
}

1.4 运行结果

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

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏