算法:求两数之和c#版本
给定一个整数数组 nums
和一个目标值 target
,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
1.暴力循环
两次for循环遍历 ,然后取值相加, 所以时间复杂度比较度,为O(n的平方)
/// <summary>
/// 暴力破解 时间复杂度O(n^2)
/// </summary>
/// <param name="nums"></param>
/// <param name="target"></param>
/// <returns></returns>
public int[] TwoSum(int[] nums, int target)
{
//List<int> result=new List<int>();
for (var i = 0; i < nums.Length; i++)
{
for (var j = i + 1; j < nums.Length; j++)
{
if (nums[i] + nums[j] == target)
{
return new int[] { nums[i], nums[j] };
//result.Add(nums[i]);
//result.Add(nums[j]);
//return result.ToArray();
}
}
}
return null;
}
2. 两次hash运算
先把值全加入hashtable表中,然后再循环,通过hash查找相减的值 ,找到对应的key,
注意不能把key值存储value值 ,因为value值可能有重复,key值不能重复,java环境中的hashmap 中,key值重复虽然不会报错但是会替换。
public int[] TwoSum2(int[] nums, int target)
{
Hashtable hsNums=new Hashtable();
for (int i = 0; i < nums.Length; i++)
{
hsNums.Add(i,nums[i]);
}
for (int i = 0; i < nums.Length; i++)
{
int complement = target - nums[i];
if (hsNums.ContainsValue(complement))
{
int j =Convert.ToInt32(hsNums.OfType<DictionaryEntry>().FirstOrDefault(x => x.Value.ToString() == complement.ToString()).Key);
if(j!=i)
return new int[]{i,j};
}
}
return null;
}
3.一次hash
通过for迭代循环,相用相减 ,找到余值,然后用hash表判断是否存在,如果不存在,则把该值和对应的索引加入hash表,如果存在,则找到对应的key值 ,返回对应的数组 。
public int[] TwoSum3(int[] nums, int target)
{
Hashtable hsNums = new Hashtable();
for (int i = 0; i < nums.Length; i++)
{
int complement = target - nums[i];
if (hsNums.ContainsValue(complement))
{
int j = Convert.ToInt32(hsNums.OfType<DictionaryEntry>().FirstOrDefault(x => x.Value.ToString() == complement.ToString()).Key);
if (j != i)
return new int[] { i, j };
}
hsNums.Add(i,nums[i]);
}
return null;
}
测试
static void Main(string[] args)
{
int[] nums = new[] {1, 2, 4, 5};
int tartget = 9;
//int[] result = new Solution().TwoSum(nums, tartget);
//int[] result = new Solution().TwoSum2(nums, tartget);
int[] result = new Solution().TwoSum3(nums, tartget);
Console.WriteLine(result[0]);
Console.WriteLine(result[1]);
Console.ReadKey();
}
还不快抢沙发