leetcode1

方案一：算法思想：两层循环。时间负责度：O(n^2)，空间复杂度O(1)。代码使用C#实现：

 1 public class Solution
 2     {
 3         public int[] TwoSum(int[] nums, int target)
 4         {
 5             var ary = new int[2];
 6             for (int i = 0; i < nums.Length; i++)
 7             {
 8                 for (int j = i + 1; j < nums.Length; j++)
 9                 {
10                     if (nums[i] + nums[j] == target)
11                     {
12                         ary[0] = i;
13                         ary[1] = j;
14                         return ary;
15                     }
16                 }
17             }
18             return ary;
19         }
20     }

方案二：算法思想：哈希。使用空间换取时间，时间复杂度：O(n)，空间复杂度：O(n)。代码使用python实现：

 1 class Solution:
 2     def twoSum(self, nums: 'List[int]', target: 'int') -> 'List[int]':
 3         s = {}
 4         for i in range(len(nums)):
 5             n = nums[i]
 6             cop = target - n
 7             if cop in s.keys():
 8                 return [s[cop],i]
 9             s[nums[i]] = i
10         return  []

算法分析：

为方便理解，先定义一个概念——“补”。

假设a + b = target，则定义：在目标为target的情况下，a 是 b 的补，同样 b 是 a 的补。

使用字典s来存储已经遍历过的数值的“补”，即目标值与已遍历的值的差。

这样在遍历到一个新值时，如果当前值与s中已经存在的key相同，则表示当前值是已经遍历过的另一个值的“补”。

则可以获得本题所要求的两个和为target的数值的下标。