two solutions:C++ unordered_map 19ms, but sort()+two pointer 9ms.why??


  • 0
    L

    Solution 1:
    using unordered_map: 19ms beat 62.52%.

    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            vector<int> res(2);
            unordered_map<int, int> m;
            for (int i = 0; i < nums.size(); i++) {
                if (m.find(target-nums[i]) != m.end()) {
                    int j = m[target-nums[i]];
                    res[0] = i < j ? i : j;
                    res[1] = i > j ? i : j;
                }
                m[nums[i]] = i;
            }
            return res;
        }
    };
    

    Solution 2:
    But using sort()+two pointer: 9ms beat 96.91

    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            vector<int> bak = nums;
            sort(nums.begin(), nums.end());
            vector<int> res;
            int i = 0, j = nums.size() - 1;
            while (i < j) {
                int sum = nums[i] + nums[j];
                if (sum == target) {
                    
                    for (int k = 0; k < bak.size(); k++) {
                        if (bak[k] == nums[i] || bak[k] == nums[j]) {
                            res.push_back(k);
                        }
                    }
                    return res;
                } else if (sum < target) {
                    i++;
                } else {
                    j--;
                }
            }
            return res;
        }
    };
    

    Anybody tell me why? I used to believe Solution1 consume less time...But ..


  • 1

    @leixinyuethu I kind of agree on your point. The latter solution will take about O(n^2) while the first only O(n). For now the only reason I see for this case is that

    • the test case is kind of small and cannot present the performance gap between these two different time complexities.

    Just a guess, waiting for more clear explanation.


  • 0
    L

    @LHearen Thanks for your explanation.


  • 0
    X

    @LHearen The latter solution is O(nlog(n))


  • -1

    @xenophobia You cannot really think the following code will only take O(n)?

              while (i < j) {
                int sum = nums[i] + nums[j];
                if (sum == target) {
                    
                    for (int k = 0; k < bak.size(); k++) {
                        if (bak[k] == nums[i] || bak[k] == nums[j]) {
                            res.push_back(k);
                        }
                    }
                    return res;
                } else if (sum < target) {
                    i++;
                } else {
                    j--;
                }
            }
    

  • 0
    X

    @LHearen So what do you think it should be? O(n^2)? You cannot blindly say it is O(n^2) when you see there is a while loop and a for loop.

    The for loop will be only executed once, not every time.


  • 0

    @xenophobia Okay, let's suppose the target = 5 and the nums will be [1, 2, 3, 4]
    In this case, what would you say the time cost of the two-level loop?


  • 1
    X

    In the example that you provides, it is not O(n) because there are more than one answers. However, the problem statement already says that "You may assume that each input would have exactly one solution.".


  • 0
    U

    in solution 1

    res[0] = i < j ? i : j;
    res[1] = i > j ? i : j;
    

    can be more concise, better to replace it by

    res[0] = j;
    res[1] = i;
    break;
    

    in solution 2
    the second

    return res;
    

    seems unnecessary.
    But I think it is better to replace the first by

    break;
    

Log in to reply
 

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