LeetCode之求两数之和

记录学习数据结构过程中练习的算法题

本题是关于数组的练习，题干清晰，难度简单，没有太多需要说明的地方

1.暴力求解

这是看到题目马上想到的解法，两层循环，直接求解，因为题目规定只会输出一个对应答案，不需要考虑其他情况

        public static int[] TwoSum(int[] nums, int target)
        {
            for (int i = 0; i < nums.Length; i++)
            {
                int temp = target - nums[i];
                for (int j = i + 1; j < nums.Length; j++)·
                {
                    if(temp == nums[j])
                    {
                        return new int[] {i,j};
                    }
                }
            }
            return new int[2];
        }

时间复杂度：O（n^2）
空间复杂度：O（1）
虽然AC，但是时间复杂度不是很满意，感觉还有优化的空间

2.利用哈希表（字典）求解

参考了其他优解，可将数组插入到字典中，然后直接检查字典中是否已经存在当前元素所对应的目标元素，如果存在，就可以直接返回对应解，这个下来，只用遍历一次即可。

        public static int[] TwoSum(int[] nums, int target)
        {
            Dictionary<int, int> dic = new Dictionary<int, int>();
            for (int i = 0; i < nums.Length; i++)
            {
                if(dic.ContainsKey(target - nums[i]))
                {
                    return new int[] { i, dic[target - nums[i]] };
                }
                dic[nums[i]] = i;
            }
            return new int[] { };
        }

时间复杂度：O（n）
空间复杂度：O（n）

最后附上题目地址：
https://leetcode-cn.com/problems/two-sum/