Two Sum


  • 2

    Click here to see the full article post


  • 0
    T

    Can we do any better than O(n) time ?


  • 4

    No. Because you need to look at each element at least once.


  • 0
    Y

    I think these articles should be accessed in each problem's page, not separated, or the problem number should be added to each title.


  • 0

    Thanks for your feedback, we will add a link to the articles from the problem page.


  • 0

    Now you can access the solution from the problem's page!


  • 0
    Y

    Thanks!


  • 0
    J

    I feel there are some mistakes in Approach #2. how about if there is repeated element in the array?


  • 0

    Great point. Since each element can be repeated at most once, an item in the table may be overwritten by the repeated item. This is fine because the answer cannot match one non-repeated element together with another repeated element.


  • 0
    Z

    Any simple way to use Hash Table in C?


  • 0

    You may use uthash, which is already included for you in C. For sample usage, you may refer here: https://troydhanson.github.io/...


  • 0
    Z

    Great!. It is truly amazing that you replied so fast:)
    Thank you so much.


  • 0
    Z

    Not sure if I can ask here..
    The submission shows my code has a runtime error:
    Last executed input:
    [0,4,3,0]
    0
    But I tested the input and get [0,3],which I think is correct, not sure what is wrong...


  • 0
    Z

    find the error, I was using a global variable.


  • 0
    C
    int* twoSum(int* nums, int numsSize, int target) {  
        for (int i = 0; i < numsSize; i++) {
            for (int j = i + 1; j < numsSize; j++) {
                if (nums[i] == target - nums[j]) {
                    int ans[2] = { i, j };  
                    return ans;  
                }
            }
        }
    }
    

    First time to be here ! Thanks leetCode!
    I do not understand why my code could not get the right output online.But it works well in VS?
    Please tell me why?


  • 0

    You can't return a static array from C. The static array is allocated on the stack memory and when the function returns, attempting to access the array's memory will cause undefined behavior. What you need to do is to allocate the array dynamically. See here for more info: http://stackoverflow.com/quest...


  • 0
    A

    For Approach #2, I set up the Testcase for [3,3,2,1] and target is 6, the output is [0,1]. I am wondering why the first key "3" is not overwritten?


  • 0

    For input [3,3,2,1] and target=6, after the first iteration the table contains the following mapping: {'3': 1, '2': 2, '1': 3}. As you can see, the mapping for the first key "3" is overwritten from 0 to 1.


  • 0
    A

    Oh yes, it is. Got it. Thank you so much.


  • 2
    B
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> sol;
        multimap<int,int> paired; //need to handle duplicates elmt
        for(int i = 0; i < nums.size(); i++){
            paired.insert(pair<int,int>(nums[i],i));
        }
        for(int i = 0; i < nums.size(); i++){
            pair<multimap<int,int>::iterator,multimap<int,int>::iterator> ret;
            ret = paired.equal_range(target-nums[i]);
            multimap<int,int>::iterator ind = paired.find(nums[i]);
            for(multimap<int,int>::iterator it = ret.first; it != ret.second; ++it){
                //handling duplicates elmt
                if(it->second != ind->second){
                    sol.push_back(ind->second);
                    sol.push_back(it->second);
                    return sol;
                }
            }
        }
        return sol;
    }
    

Log in to reply
 

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