算法：求两数之和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();
 }

参考：https://leetcode.com/problems/two-sum/solution/