[LeetCode] - Two Sum

 1         /// <summary>
 2         /// 暴力解O(n2)
 3         /// </summary>
 4         /// <param name="nums"></param>
 5         /// <param name="target"></param>
 6         /// <returns></returns>
 7         public static int[] TwoSum(int[] nums, int target)
 8         {
 9             int[] result = new int[2];
10             for (int i = 0; i < nums.Length; i++)
11             {
12                 for (int j = i + 1; j < nums.Length; j++)
13                 {
14                     if (nums[i] + nums[j] == target)
15                     {
16                         result[0] = i;
17                         result[1] = j;
18                         break;
19                     }
20                 }
21             }
22 
23             return result;
24         }    

 1         /// <summary>
 2         /// two pass hashtable 解, O(1)，如果有碰撞(collision)則為O(n)
 3         /// 因為先把所有數放進hashtable，有可能找到自已
 4         /// </summary>
 5         /// <param name="nums"></param>
 6         /// <param name="target"></param>
 7         /// <returns></returns>
 8         public static int[] TwoSum2(int[] nums, int target)
 9         {
10             Dictionary<int, int> map = new Dictionary<int, int>();
11 
12             for (int i = 0; i < nums.Length; i++)
13             {
14                 map[nums[i]] = i;
15             }
16 
17             for (int i = 0; i < nums.Length; i++)
18             {
19                 //餘數
20                 int complement = target - nums[i];
21 
22                 if (map.ContainsKey(complement) && map[complement] != i)
23                 {
24                     //當前數的index & 餘數的index
25                     return new int[] { i, map[complement] };
26                 }
27             }
28 
29             throw new ArgumentNullException();
30         }

 1 　　　　　/// <summary>
 2         /// one pass hashtable
 3         /// hashtable內永遠只有 nums[i-1],nums[i-2]...的數，不會找到自已
 4         /// </summary>
 5         /// <param name="nums"></param>
 6         /// <param name="target"></param>
 7         /// <returns></returns>
 8         public static int[] TwoSum3(int[] nums, int target)
 9         {
10             Dictionary<int, int> map = new Dictionary<int, int>();
11 
12             for (int i = 0; i < nums.Length; i++)
13             {
14                 int complement = target - nums[i];
15                 if (map.ContainsKey(complement))
16                 {
17                     return new int[] { map[complement], i };
18                 }
19 
20                 map[nums[i]] = i;
21             }
22 
23             throw new ArgumentException();
24         }