LeetCode-220. Contains Duplicate III

LeetCode-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 absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3Output: false

题解：

使用一个容器存储每个数和它的下标。

然后排序，一是减小搜索量，二是防止溢出（set寻找一直爆）。

遍历数组找到第一个满足nums[i] + t >= nums[j]的，判断其下标是否在k内。

class Solution {public: bool containsNearbyAlmostDuplicate(vector& nums, int k, int t) { vector>dup; int n = nums.size(); for (int i = 0; i < n; i++) { dup.push_back({nums[i], i}); } sort(dup.begin(), dup.end()); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (dup[i].first + t >= dup[j].first) { if (abs(dup[i].second - dup[j].second) <= k) { return true; } } else { break; } } } return false; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。