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的代碼語義相當簡潔易懂