Leetcode-1.Two Sum

题目连接：

https://leetcode-cn.com/problems/two-sum/

C#实现

• 暴力法

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        for(int i = 0;i < nums.Length - 1;i ++) {
            for(int j=i+1;j<nums.Length;j++){
                if (nums[i] + nums[j] == target){
                    return new int[2] {i,j};
                }
            }
        }
        return new int[2];
    }
}
           

• hash法

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Hashtable ht=new Hashtable();
        for(int i = 0;i < nums.Length;i ++) {
            int complement = target - nums[i];
            if(ht.ContainsKey(complement)){
                return new int[] {Convert.ToInt32(ht[complement]), i};
            }
            ht[nums[i]] = i;
        }
        throw new Exception("No result");
    }
}
           

python实现

• 暴力法

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        nums_len = len(nums)
        for i in range(nums_len - 1):
            for j in range(i + 1, nums_len):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []
           

• hash法

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        map = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in map.keys():
                return [map[complement], i]
            map[nums[i]] = i
        return []
           

官方解析：

https://leetcode-cn.com/problems/two-sum/solution/

这个题目如果使用暴力法，其实很简单，但就算法而言并不是一个好的方法。官方题解给出了三种方式的解析，这里不再复述。需要注意的是，题目中给定的假设：假设每种输入只会对应一个答案。这就避免了一个多解的问题，从而避开了数组中有重复值导致多解，我们只管求出一个解就可以。以数组值作为hashmap的key时，如果key重复无法求出多个解。

在使用C# hashtable时同样也要注意，如果key重复，在Add方法时会抛出异常。

一个有意思的事情：在这道题中使用了C#和python两种语言实现，可以看到python的代码语义相当简洁易懂