Блог

Я решаю проблему -> Учитывая массив целых чисел, выясните, есть ли в массиве два разных индекса i и j, так что абсолютная разница между числами [i] и числами [j] не превышает t, а абсолютная разница между i и j не превышает k.

и ошибка, которую я получаю, — строка 16: Символ 17: ошибка времени выполнения: индекс 3 выходит за пределы для типа ‘int [n — 1]’ (solution.cpp ) СВОДКА: UndefinedBehaviorSanitizer: неопределенное поведение prog_joined.cpp:25:17

Строка 16 — это индекс [i][j] = abs(i-j);

 class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>amp; nums, int k, int t) {
     
    
            
    int n = nums.size();
        
        int indice[n-1][n-1];
        int  total[n-1][n-1];

        for(int i = 0;i<n;i  )
        {
            for(int j=0;j<n;j  )
            {
                indice[i][j]= abs(i-j);
                total[i][j] = abs(nums[i]-nums[j]);
           
            }
        }
        
        
        for(int i = 0;i<n;i  )
        {
            for(int j=0;j<n;j  )
            {
        if(indice[i][j]<=k amp;amp; total[i][j]<=t)
        {
                return true;
        }
            }
        }
        
        
        
        
return false;        
    }
};
  

для тестового примера [1,2,3,1] 3 0

Код отлично работает на моем устройстве и другом компиляторе, но не на компиляторе leetcode.

Пожалуйста, помогите

Это исправило бы вашу ошибку, однако существует проблема с вашим алгоритмом, не проходит все тестовые случаи:

 class Solution {
    public:
        bool containsNearbyAlmostDuplicate(vector<int>amp; nums, int k, int t) {



            int n = nums.size();

            int indice[n][n];
            int  total[n][n];

            for (int i = 0; i < n; i  ) {
                for (int j = 0; j < n; j  ) {
                    indice[i][j] = abs(i - j);
                    total[i][j] = abs(nums[i] - nums[j]);

                }
            }


            for (int i = 0; i < n; i  ) {
                for (int j = 0; j < n; j  ) {
                    if (indice[i][j] <= k amp;amp; total[i][j] <= t) {
                        return true;
                    }
                }
            }




            return false;
        }
};

  

Это решение будет проходить с использованием std::lower_bound :

 // The following block might trivially improve the exec time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    return 0;
}();

// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>
#include <set>
#include <algorithm>

using ValueType = std::int_fast64_t;

static const struct Solution {
    static const bool containsNearbyAlmostDuplicate(
        const std::vector<int>amp; nums,
        const int k,
        const int t
    ) {
        std::set<ValueType> window;
        ValueType len = std::size(nums);

        for (auto index = 0; index < len;   index) {
            if (index > k amp;amp; index - k - 1 < len ) {
                window.erase(nums[index - k  - 1]);
            }

            const auto it = window.lower_bound((ValueType)nums[index] - t);

            if (it != std::cend(window) amp;amp; *it - nums[index] <= t) {
                return true;
            }

            window.insert(nums[index]);
        }

        return false;
    }
};