Why my O(N^2) beats 96.4%?


  • 0

    Here is my solution:

        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            if (!nums.size()) return false;
            vector<pair<long long, int> > sorted;
            for (int i = 0; i < nums.size(); ++i) {
                sorted.push_back(make_pair(nums[i], i));
            }
            sort(sorted.begin(), sorted.end());
            for (int i = 0; i < sorted.size(); ++i) {
                for (int j = i + 1; j < sorted.size() 
                     && sorted[j].first - sorted[i].first <= t; ++j) {
                    if (abs(sorted[i].second - sorted[j].second) <= k) return true;
                }
            }
            return false;
        }
    

Log in to reply
 

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