My nlog(n) solution, only O(N) space, but meets Memory Limit Exceeded, anyone can tell me why?


  • 0
    M
    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
        	int n = nums.size();
        	vector<int> idx(n);
        	iota(idx.begin(), idx.end(), 0);
        	sort(idx.begin(), idx.end(), [nums](int l, int r) {return nums[l] < nums[r]; });
        	for (int i = 0; i < n; ++i) {
        		int dif = target - nums[idx[i]];
        		if (dif < nums[idx[i]]) continue;
        		else {
        			int l = i + 1;
        			int r = n - 1;
        			int m = (l + r) / 2;
        			while (l <= r) {
        				if (nums[idx[m]] == dif) {
        					vector<int> res = { max(idx[i], idx[m]), min(idx[i], idx[m]) };
        					return res;
        				}
        				else if (nums[idx[m]] < dif) {
        					l = m + 1;
        					m = (l + r) / 2;
        				}
        				else {
        					r = m - 1;
        					m = (l + r) / 2;
        				}
        			}
        		}
        	}
        }
    };

  • 1
    K

    In the sort function, you shall capture the variable nums by reference. That is

    sort(idx.begin(), idx.end(), [&nums](int l, int r) {return nums[l] < nums[r]; });

  • 0
    M

    Thank you , that is the problem.


Log in to reply
 

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