1.两数之和

LeetCode LeetCode 数组 哈希表 热题100
发布时间 :
字数:3.4k 阅读 : 评论:
  1. 1.两数之和
    1. 1.1 题目
    2. 1.2 题解
      1. 方法一：暴力法
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：两遍哈希表
        1. 思路
        2. 复杂度分析
        3. 代码
      3. 方法三：一遍哈希表
        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 题解

方法一：暴力法

思路

最直观的做法：用两层循环遍历所有可能的数字对。

具体步骤：

  1. 外层循环选择第一个数字 nums[i]
  2. 内层循环从 i + 1 开始选择第二个数字 nums[j]
  3. 检查两者之和是否等于 target，找到答案就立即返回

为什么 j 从 i + 1 开始？

  • 题目要求不能使用同一个元素两次
  • nums[i] + nums[j] 与 nums[j] + nums[i] 是同一对组合，没必要重复检查

举个例子：假设 nums = [2, 7, 11, 15]，target = 9

  • i = 0 时，检查 nums[0] + nums[1] = 2 + 7 = 9，正好等于 target，返回 [0, 1]

复杂度分析

  • 时间复杂度：O(n^2)，最坏需检查约 n(n-1)/2 对
  • 空间复杂度：O(1)，只使用常数额外变量

代码

//方法一：暴力法
//使用两层循环遍历数组中的每一对数字组合，检查相加是否等于目标值。如果找到符合条件的数字，返回它们的索引数组。
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 };
}

方法二：两遍哈希表

思路

暴力法的问题在于「查找配对元素」需要 O(n) 时间。如果用哈希表把「值 → 下标」存起来，查找就能降到 O(1)。

两遍遍历分工明确：

第一遍：建表

  • 把每个元素的值和下标存入字典
  • 遇到重复值时，如果该值的两倍恰好等于 target，直接返回这两个下标

第二遍：配对

  • 对每个位置 i 计算 target - nums[i]
  • 看字典里是否存在这个差值，且下标不等于 i
  • 找到就返回答案

举个例子：假设 nums = [3, 2, 4]，target = 6

  • 第一遍建表：{3: 0, 2: 1, 4: 2}
  • 第二遍配对：i = 0 时，找 6 - 3 = 3，存在但下标相同；i = 1 时，找 6 - 2 = 4，存在且下标不同，返回 [1, 2]

复杂度分析

  • 时间复杂度：O(n)，两次线性扫描
  • 空间复杂度：O(n)，字典最多与数组规模同阶

代码

// 方法二：两遍哈希表
// 第一遍循环：将数组元素及其索引添加到字典中。如果发现相同值的元素，判断值乘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 };
}

方法三：一遍哈希表

思路

在遍历数组的同时，用哈希表记录「已经见过的数值 → 下标」。这样每个元素只处理一次，且不会用到同一元素两次。

具体步骤：

  1. 对每个位置 i，先看表里有没有 target - nums[i]
  2. 有则说明和为 target 的另一端已在前面出现过，直接返回两个下标
  3. 没有则把当前值和下标放进表，继续往后

举个例子：假设 nums = [2, 7, 11, 15]，target = 9

  • i = 0：找 9 - 2 = 7，表里没有，存入 {2: 0}
  • i = 1：找 9 - 7 = 2，表里有！返回 [0, 1]

为什么一遍就够了？

  • 因为答案只有一对，当我们遍历到第二个数时，第一个数已经在表里了
  • 不需要等所有元素都入表再查找

复杂度分析

  • 时间复杂度：O(n)，每个元素常数次字典操作
  • 空间复杂度：O(n)，字典规模不超过数组长度

代码

//方法三：一遍哈希表
//遍历数组时判断哈希表有没有需要的差值，没有就存储数组元素的值和索引到字典。注意重复值判断。
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 输出：[{result12[0]}, {result12[1]}]");
        Console.WriteLine($"示例1 方法3 输出：[{result13[0]}, {result13[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-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏