折腾一个Two_Sum（上）

11 Jan 2018

在这篇文章里，我用了10个计算机语言解决一个算法小问题。再看了下Leetcode执行它们的性能。

Two Sum题干：

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice. Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

两层for循环，最天真，是因为时间复杂度最高O(n²)，但是不能忘它是空间复杂度最低的O(1)。但是最天真的遍历不代表它没什么好折腾的。可以换语言写写。

C++解一：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        for (int i=0; i<nums.size(); ++i){
                for(int j=i+1; j<nums.size(); ++j){
                        if( nums[i]+nums[j] == target ){
                                result.push_back(i);
                                result.push_back(j);
                                return result;
                        }
                }
        }
        throw std::invalid_argument("No solution");
    }   
};

Performance: 190ms

Python2.x/3.x解一：

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

Performance: python2 5543ms / python3 time out

Java解一：

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++){
                if (nums[i]+nums[j] == target){
                    return new int[] { i,j };
                }
            }
        }
        throw new IllegalArgumentException("No solution");
    }
}

Performance: 43ms

C解一：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 **/
int* twoSum(int* nums, int numsSize, int target) {
    static int result[2] = { -1,-1 };
    for(int i = 0; i < numsSize; i++)
    {
        for(int j = i+1; j < numsSize; j++)
        {
            if(nums[i]+nums[j] == target)
            {
                result[0] = i ;
                result[1] = j ;
                return result;
            }
        }
    }
    return NULL;
}

Performance: 103ms

C#解一:

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++){
                if (nums[i]+nums[j] == target){
                    return new int[] { i,j };
                }
            }
        }
        throw new ArgumentNullException("No solution");
    }
}

Performance: 805ms

Javascript解一：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 **/
var twoSum = function(nums, target) {
    for (var i=0; i<nums.length; i++){
        for (var j=i+1; j<nums.length; j++){
            if (nums[i]+nums[j] === target){
                return [i,j];
            }
        }
    }
    throw new Error("No solution");
};

Performance: 200ms

Ruby解一:

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
  nums.each_with_index do |num1, i|
    nums[i+1..-1].each_with_index do |num2, j|
      return [i, i+j+1] if num1 + num2 == target
    end
  end
  return "No solution"
end

Performance: 5624ms

Swift解一：

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var result = [Int]()
         for i in 0..<nums.count {
            for j in i+1..<nums.count {
                if nums[i] + nums[j] == target {
                    result.append(i)
                    result.append(j)
                    return result
                }                
            }
         }
         return result  
    }
}

Performance: 947ms

Golang解一：

func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] + nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}

Performance: 63ms

Kotlin解一：

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        for( i in 0..nums.size-1){
            for( j in i+1..nums.size-1){
                if(nums[i] + nums[j] == target){
                    return intArrayOf(i,j)
                }
            }
        }        
        return intArrayOf()
    }
}

Performance: 593ms

Home Studio不专业分析：

蛮无聊的吧，每个代码我都尽力让他们相近了，Ruby, Swift, Golang和Kotlin全部都不懂异常，就被我忽悠了。过去学语言都掉进了语法这个白痴的误区里，我现在问我自己它们之间有啥各自的语法特性和优劣，我根本就说不出来，很衰。所以唯一的意义是温习了一遍语法，不过我把它们都送到Leetcode里去运行了，从过去有限的刷题经验上看各种语言的测试集是一样的。整理了它们的运行时间绘制了一张图。 placeholder

关于正式的计算机语言Benchmark看 The Computer Language Benchmarks Game 。

图和Benchmark比较，除了Java和Go快的不正常，C++看起来有点慢，但是不知道编译器，Python真是不济，其他排序还挺理性。我想，

Leetcode里的Java和Go，不管它是什么，但应该不是CPU运行时间。
Python3直接Time Out，在单独的手动测试集上Python3竟然比Python2慢将近一倍。这个真意外。

关于这篇博客一些有意思的东西：

这是我fork Hyde 后修改的一个Github Page
博文是我在 Vim 里搭配插件 livemark.vim 直接码的，目的是熟悉下 Jerkll 的Markdown
图表是在 Infogram 里生成的
题目和测试都是在 Leetcode 上进行的，用了 Leetcode-cli 把代码本地化
期间把阿狗忘记，以至于它被泡在洗衣粉里一晚
一直单曲重复Luca Brasi的 Theme Song from Hq
发现Markdown定义的符号里嵌套html的tag会失败，这样的O(n<sup>2</sup>)和 O(n²)

如果有建议，观点或者问题的话，可以给我发邮件aileen365@gmail.com，因为我还不知道该怎么在静态网页里设留言板，有主意欢迎告诉我。

Not a Genius