LeetCode 第一题: 两数之和

[shunfy]

LeetCode 第一题: 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

#include <map>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> tmpMap;
        int tmpNumber;
        for(int i=0, imax = nums.size(); i<imax; ++i)
        {
            tmpNumber = nums[i];
            if(tmpMap.find(tmpNumber) != tmpMap.end())
                return { tmpMap[tmpNumber], i };
            else
                tmpMap[target - tmpNumber] = i;
        }
        return {};
    }
};

以上是 Java 代码,LeetCode 执行时间是 4ms.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> tmpMap = new HashMap<>();
        int tmpNumber;
        for(int i=0, imax = nums.length; i<imax; i++)
        {
            tmpNumber = nums[i];
            if(tmpMap.containsKey(tmpNumber))
                return new int[]{tmpMap.get(nums[i]), i};
            tmpMap.put(target - nums[i], i); 
        }
        return null;
    }
}

以上是 Java 代码,LeetCode 执行时间是 0ms.

using System.Collections.Generic;

public class Solution
{
    public int[] TwoSum(int[] nums, int target)
    {
        Dictionary<int, int> tmpTab = new Dictionary<int, int>(1);
        int tmpNumber;
        for (int i = 0, imax = nums.Length; i < imax; ++i)
        {
            tmpNumber = nums[i];
            if (tmpTab.ContainsKey(tmpNumber))
                return new int[] { tmpTab[tmpNumber], i };
            else
                tmpTab[target - tmpNumber] = i;
        }

        return null;
    }
}

以上是 CS 代码,执行时间竟然有 300ms

---

为什么执行时间会相差这么大呢? 是因为 LeetCode 的执行环境问题吗? 此逻辑还有优化的空间吗?

[lewis89]

leetcode 代码执行时间 你就当个笑话看就是了

[Jirajine]

你要比较，也得给足够大的数据集，多次运行，取平均时间，以排除冷启动、缓存等因素造成的干扰。

[shunfy]

@lewis89 你说的可能是对的

[ch2]

刘翔和博尔特比赛跑 1 米，我哨子吹完开始计时，博尔特愣了一下，成绩慢了 300ms

[shpkng]

LeetCode 同一段代码的执行速度都能差一半的

[Chenamy2017]

多跑几次，取平均值看看

[obtain]

比较时间执行的快慢没意义的，要比较写的算法时间复杂度。