LeetCode 1. Two Sum

给定一个整数数组，返回两个数字的索引，使得它们加起来等于一个特定的目标值。 您可以假设每个输入都有一且只有一个答案，数组中每个元素只能使用一次。 Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

　　

using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { int[] nums = { 7, 11, 15 ,2}; int target = 9; var numarr = TwoSum(nums, target); } // right hash: time O(n) (degenerate when collison occured) ususlly O(1) (insert and search) space: O(n) result: 496ms public static int[] TwoSum(int[] nums, int target) {

int[] result = new int[2]; //[0,3],[3,0] Dictionary<int, int> table = new Dictionary<int,int>(); // use empty constructor, result: 544 ms for (int i = 0; i < nums.Length; i++) { int another = target - nums[i]; if (table.ContainsKey(another)) { int anotherIndex = table[another]; result[0] = anotherIndex > i ? i : anotherIndex; result[1] = anotherIndex < i ? i : anotherIndex; return result; } else { if (!table.ContainsKey(nums[i])) { table.Add(nums[i], i); } } }

throw new Exception("no answer");

} } }

　　

转载于:https://www.cnblogs.com/c-x-a/p/8144870.html