由于 LeetCode 上的“if”语句，相同的代码超时

Question

的问题是从本文给出了拍摄中，我们必须找出是否有两个不同的指数i和阵列以J，使得绝对之间差NUMS [I]和NUMS [j]的是至多吨和我之间的绝对差j至多为k。我的方法是 O(N*N) 这不应该是可以接受的，但它是。

接受的代码：

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

    return false;
}

给出超时的代码：

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

    return false;
}

我不明白为什么第一个代码运行效率高（按照 leetcode）而第二个代码给出了 TLE？唯一的区别是在循环内使用条件“IF”语句，我认为这不是很昂贵。

问题链接：https : //leetcode.com/problems/contains-duplicate-iii/

Answer 1

如果我们将其归结为必不可少的，那么您正在比较

for (int i = 0; i < imax; ++i) {
   if ( some_condition(i) ) {
       // do something
   }
}

对比

for (int i = 0; i < imax && some_condition(i); ++i) {
    // do something
}

第二个循环终止一次some_condition(i)，false而第一个循环总是运行所有迭代。

当你马虎不注意细节时，代码是非常不可原谅的：

唯一的区别是在循环内使用了条件“IF”语句

不，这不是唯一的区别！