每日一算法之two sum

题目如下：首先准备一个数组,[1,2,8,4,9] 然后输入一个6，找出数组两项之和为6的两个下标。

啥也不想，马上上代码，这个太简单了，

   static int[] twoSum(int[] nums, int target){

            for (var i = 0; i < nums.Length; i++) {

                for (int j = 0; j < nums.Length; j++) {

                    if (nums[i] + nums[j] == target) {

                       return new int[] {i,j};

                    }

                }

            }

            throw new Exception("No Sum Solution");

        }

从这里我们可以看出，这个算法的时间复杂度是O(n的平方),这里有双重循环了。

既然这个算法不好，循环太多次了，那我们就得想办法减少循环，减少时间复杂度，然后就有了如下代码。

        static int[] twoSum(int[] nums, int target) {

            int[] result = new int[2];

            Dictionary<int, int> dict = new Dictionary<int, int>();

            for (var i = 0; i < nums.Length; i++) {

                if (dict.ContainsKey(target - nums[i])) {

                    result[0] = Convert.ToInt32(dict[target - nums[i]]);

                    result[1] = i;

                    return result;

                }

                if (!dict.ContainsKey(nums[i])) { //这个是为了防止有重复的情况出现。

                    dict.Add(nums[i], i);

                }

            }

            return result;

        }

巴特西

每日一算法之two sum

最新文章

热门文章