O(n) C++ code which defeats 98%


  • 10
    A
    Maybe helpful for someone.    
    class Solution 
    {
    public:
        vector<int> twoSum(vector<int>& nums, int target) 
        {
            static int MAX = 99999;
            static int DELT = 49999;
            vector<int> ans;
            int x[MAX];
            memset(x, 0, sizeof(x));
            for (int i = 0; i < nums.size(); i++)
            {
                if (x[nums[i] + DELT])
                {
                    ans.push_back(((i + 1) < x[nums[i] + DELT] ? 
                                              (i + 1) : x[nums[i] + DELT]));
                    ans.push_back(((i + 1) > x[nums[i] + DELT] ? 
                                              (i + 1) : x[nums[i] + DELT]));
                    return ans;
                }
                x[target - nums[i] + DELT] = i + 1;
            }
        }
    };

  • 1
    N

    What's the story for magic number 99999 and 49999


  • 0
    P

    a good answer for less time! But I think that the condition expression may be useless in the function.


  • 1
    P

    I suppose they just large numbers which make the index non-negative. You can only get them by trail and error because the range of input is unknown.


  • 0
    J

    I think so ! The question says index1 must be less than index2,and the number in x[] is less than the current i.I have modified it and it is accepted.


  • 0
    H

    If the input range is big enough, I think index will be negative.


  • 0
    Z

    I feel like this is kind of a hack, since you basically use a long array as the hashtable, and simply put the numbers into this array. Please correct me if I am wrong.


  • 0

    I run this code in Xcode, it says Control may reach end of non-void function.


Log in to reply
 

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