Why my code is running so slow?


  • 0
    L

    This is my code tooks 12ms to solve this problem.

    int threeSumClosest(std::vector<int>& nums, int target) 
    {
        if (nums.size() == 3)
            return nums[0] + nums[1] + nums[2];
        int ret{ 2147483647 };
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 2;i++)
        {   
            int l = i + 1, u = nums.size() - 1;
            while (l < u)
            {
                int distance = nums[l] + nums[u] + nums[i] - target;
                ret = abs(ret) < abs(distance) ? ret : distance;
                if (distance > 0)
                    u--;
                else if (distance < 0)
                    l++;
                else
                    return target;
            }
        }
        return ret + target;
    }
    

    This is another code only tooks 6ms to solve this problem.

        int threeSumClosest(vector<int>& nums, int target) {
            if (nums.size() == 3)
    			return nums[0] + nums[1] + nums[2];
    
    		sort(nums.begin(), nums.end());
    		int result = 10000;
    		int result_tmp = 10000;
    		for (int i = 0; i < nums.size() - 2; i++)
    		{
    			int left = i + 1;
    			int right = nums.size() - 1;
    			while (left < right)
    			{
    				int tmp = nums[i] + nums[left] + nums[right] - target;
    				result_tmp = (abs(result_tmp) < abs(tmp)) ? result_tmp : tmp;
    				if (tmp < 0)
    					left++;
    				else if (tmp > 0)
    					right--;
    				else
    					return target;
    			}
    		}
    		return result_tmp + target;
        }
    

    I think the two codes use the same algorithm and have the same time complexity(O(N*N)). The two codes also have the same logic. Why the first code is so slow?
    Note: The first code took 12ms, the second only 6ms.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.