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
