题目
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
本人使用C#语言解题，在暴力解法中，使用嵌套循环可解，时间复杂度为O（n2）,如下
public class Solution { public int[] TwoSum(int[] nums, int target) { for (int i = 0; i < nums.Length; i++) { for (int j = i + 1; j < nums.Length; j++) { int temp; temp = nums[i] + nums[j]; if (temp == target) { return new int[2] { i,j}; } } } throw new System.Exception("No two sum solution"); } }在优化解法中，java语言可以使用哈希表存储数组的值，然后利用目标值与数组值的差值去哈希表中查找，无需嵌套循环，时间复杂度为O（n），如下
class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement) && map.get(complement) != i) { return new int[] { i, map.get(complement) }; } } throw new IllegalArgumentException("No two sum solution"); } } 作者：LeetCode 链接：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。不过在C#中，我利用类似的字典Dictionary求解遇到问题，即字典的键不允许重复，如果将数组的值作为字典键，数组索引作为字典值，那么遇到有重复数字的数组即会报错。如下数组{2，2，7，9}，求和4
public class Solution { public int[] TwoSum(int[] nums, int target) { Dictionary<int,int> list = new Dictionary<int, int>(); for(int i=0;i<nums.Length;i++) { list.Add(nums[i],i); } for(int j=0; j < nums.Length;j++) { int temp = target - nums[j]; if(list.ContainsKey(temp)&& list[temp]!=j) { return new int[2] { j,list[temp] }; } } throw new System.Exception("No two sum solution"); } }若将数组的索引作为字典键，数组值作为字典值，那么又会遇到无法通过字典的值去找键的问题（除非引入命名空间using System.Linq），如下参考
using System.Linq; Dictionary<int,int> dic = new Dictionary<int,int>(); for (int i = 0; i < nums.Length; i++) dic.Add(i,nums[i]);//0,4 1,2 2,6 for (int i = 0; i < nums.Length; i++) { int vv = target - nums[i]; if (dic.ContainsValue(vv)) { var d = dic.Where(p => p.Value == vv).Select(p => p.Key).Except(new List<int> { i }); if(d.Count()>0) { return i < d.ToArray()[0] ? new int[] { i, d.ToArray()[0] } : new int[] { d.ToArray()[0], i }; } } } 作者：xiao-xu-10 链接：https://leetcode-cn.com/problems/two-sum/solution/33-426-zhu-yi-zhe-liang-chong-qing-kuang-ru-guo-yo/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。如果使用列表存储数组值，之后再查找，经测试，效率还不如暴力解法的两次嵌套循环，因为list.IndexOf（）函数本身就是一种遍历方法（详情可参考：List 底层源码剖析.）。如
public class Solution { public int[] TwoSum(int[] nums, int target) { List<int> list = new List<int>(); for(int i=0;i<nums.Length;i++) { list.Add(nums[i]); } for(int j=0; j < nums.Length;j++) { int temp = target - nums[j]; if(list.Contains(temp)&&list.IndexOf(temp)!=j) { return new int[2] { j,list.IndexOf(temp) }; } } throw new System.Exception("No two sum solution"); } }所以对于C#中本题的优化解法本人依然存疑，求路过大佬指点。
另：C#中hashtable类似，它继承有IDictionary，其实本身就是在Dictionary上实现的。
（本篇他人代码已注明转载出处）
