leetCode练习1

　　代码主要采用C#书写

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

　　你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

　　示例:

　　给定 nums = [2, 7, 11, 15], target = 9

　　因为 nums[0] + nums[1] = 2 + 7 = 9
　　所以返回 [0, 1]
　　　　分析过程：
　　　　从一个整数数组中，查找出一组满足指定和的数组成员下标。我们最开始想到的暴力算法，即：双循环找到这样的数组，然后return。
       (1)暴力算法，代码如下：

public int[] TwoSum1(int[] nums, int target) {
        List<int> listArry = new List<int>();
            if(nums != null && nums.Length > 1)
            {
                for(var i=0;i<nums.Length - 1;i++)
                {
                    for(var j = i + 1;j < nums.Length;j++)
                    {
                        if ((nums[i] + nums[j]) == target)
                        {
                            listArry.Add(i);
                            listArry.Add(j);
                            return listArry.ToArray();
                        }
                    }
                }
            }
            return listArry.ToArray();
    }

　　暴力代码的注意事项，第一个循环的下标和第二个循环的下标关系，我这样写法可以保证每次循环第一个数和它下面的所有数进行相加判断。

　　暴力代码的时间复杂度为O（n^2）空间复杂度为O（1）适合初级程序员，作为有追求的我们，要写出时间复杂度更小的高质量代码。

(2) 借助字典，将复杂度降低到O（n）

public static int[] TwoSum2(int[] nums, int target)
        {
            List<int> listArry = new List<int>();
            if (nums != null && nums.Length > 1)
            {
                //设计一个字典
                Dictionary<int, int> dicNum = new Dictionary<int, int>();//键是数组的值，值是对应的数组下标
                for(var i=0;i<nums.Length;i++)
                {
                    int complement = target - nums[i];
                    if(dicNum.Keys.Contains(complement))//最差的情况下，在最后一次循环的时候，可以通过字典找到匹配的对。这个时候时间复杂度是O（n）
                    {
                        listArry.Add(dicNum[complement]);
                        listArry.Add(i);
                        listArry.Sort();
                        return listArry.ToArray();
                    }

                    if (!dicNum.Keys.Contains(nums[i]))//判断当前的下标是否在字典的keys里，不在的话先添加。
                    {
                        dicNum[nums[i]] = i;
                    }
                }
            }

            return listArry.ToArray();

        }

　　算法二将时间复杂度降低到了O（n），但相应的增大了空间的开销到了O（n）