LeetCode-Two Sum

最近准备开始刷一些 LeetCode 的题目，从简单的开始，第一题是 Two Sum。

前一阵问小伙伴，被告知 C#在 LeetCode 上不是很好用，所以这次就选了 Python 作为实现语言。

思路一：最脑残的方法，直接表达题目的意思

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

        for i in range(len(nums)):
            for j in range(len(nums)):
                if i==j:
                    continue;
                if nums[i]+nums[j]==target:
                    return [i,j]

O(n^2)的效率，有时候能过，不过在运行一些算例的时候会超时，上次成功用了 725ms 思路二：改进了一下循环，减少了很多无谓的比较

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i]+nums[j]==target:
                    return [i,j]

修改以后，效果也还不错，用时 569ms 思路三：利用 Python 的哈希表（Dict）数据结构

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        sumDict={}
        for i in xrange(len(nums)):
            n=nums[i]
            if target-n in sumDict:
                return [sumDict[target-n],i]
            sumDict[n]=i

这一种应该算是我能想到的最简单的算法了，在看了一些网上的答案以后，感觉都是实现了一个哈希表，表现的结果应该大同小异。最终用时 408ms。

改用 Java 重写

继续 Python 的思路，双层 for 循环：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ret=new int[2];
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j]==target){
                    ret[0]=i;
                    ret[1]=j;
                    break;
                }
            }
        }
        return ret;
    }
}

使用 Java 的哈希表改成单层 for 循环：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> hm=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            int minu=target-nums[i];
            if(hm.containsKey(minu)){
                return new int[] {i,hm.get(minu)};
            }else{
                hm.put(nums[i],i);
            }
        }
        throw new IllegalArgumentException("No solution");
    }
}

运行时间为 5ms 左右。