LeetcCode #220 Contains Duplicate III

本文主要是介绍LeetcCode #220 Contains Duplicate III，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] andnums[j] is at mostt and the difference betweeni andj is at mostk.

        本题的Tags是BST，可写BST有点麻烦，其实比较简单的一个思路是，可以定义一个结构体，分别保存nums中元素的值val和下标index，然后对此结构体构成的数组根据val的大小排序，这样就很方便地同时计算  k  值和 t  值了。

       实际上用C++写时，vector中元素的地址值本身就可以作下标用，所以也就没必要再去定义这个结构体了。由此，第一次写好的代码如下：

bool cmp_ptr(int *a, int *b){return *a < *b;
}class Solution {
public:bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {const int n = nums.size();if(n <= 1 || k == 0) return false;vector<int*> num_ptrs(n);for(int i = 0; i < n; i++)  num_ptrs[i] = &nums[i];sort(num_ptrs.begin(), num_ptrs.end(), cmp_ptr);for(int i = 0; i < n; i++){for(int j = i + 1; j < n; j++){if(*num_ptrs[j] - *num_ptrs[i] > t) break;                    //the difference between nums[i] and nums[j] is at most tif(abs(num_ptrs[j] - num_ptrs[i]) <= k) return true;          //the difference between i and j is at most k}}return false;}
};

       本地测试没问题后，提交上去，又来了一个在最后一个case上WA！

      不过WA的这个case给了我充足的提示：

              显然是*num_ptrs[j] - *num_ptrs[i] > t 这个判断条件 在INT_MAX - （-1）时溢出了。

       还好leetcode在WA时都给出出错的测试用列，不然根本不可能找到自己代码是在哪个地方死的。

修改后的代码如下，时间是20ms。

bool cmp_ptr(int *a, int *b){return *a < *b;
}class Solution {
public:bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {const int n = nums.size();if(n <= 1 || k == 0) return false;vector<int*> num_ptrs(n);for(int i = 0; i < n; i++)  num_ptrs[i] = &nums[i];sort(num_ptrs.begin(), num_ptrs.end(), cmp_ptr);for(int i = 0; i < n; i++){for(int j = i + 1; j < n; j++){if(*num_ptrs[j] > *num_ptrs[i] + t) break;                    //the difference between nums[i] and nums[j] is at most tif(abs(num_ptrs[j] - num_ptrs[i]) <= k) return true;          //the difference between i and j is at most k}}return false;}
};

另外在Discuss里发现有人用set做了个滑窗，这个思路也挺好，代码量要少很多。不过相对于上一个方法，效率要低些，AC的时间是48ms。

class Solution {public:bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {set<int> window; // set is ordered automatically for (int i = 0; i < nums.size(); i++) {if (i > k) window.erase(nums[i-k-1]); // keep the set contains nums i j at most k// -t <= x - nums[i] <= t;auto pos = window.lower_bound(nums[i] - t); // x >= nums[i] - tif (pos != window.end() && *pos - nums[i] <= t) // x <= nums[i] + treturn true;window.insert(nums[i]);}return false;}
};

这篇关于LeetcCode #220 Contains Duplicate III的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---