217-存在重复元素

LeetCode 217. 存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]
输出：true

method

排序+判断

bool containsDuplicate(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); ++i) {
        if (i > 0 && nums[i] == nums[i - 1]) return true;
    }
    return false;
}

---

LeetCode 219. 存在重复元素 II

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,1], k = 3
输出：true

method

哈希表保存出现过的数字的下标，如果当前元素与之前出现的下标只差大于k，就更新数字下标

bool containsNearbyDuplicate(vector<int>& nums, int k) {
    unordered_map<int, int> hash;
    for (int i = 0; i < nums.size(); i++) {
        if (hash.find(nums[i]) != hash.end()) {
            if (i - hash[nums[i]] <= k) return true;
        }
        hash[nums[i]] = i;
    }
    return false;
}

---

LeetCode 220. 存在重复元素 III

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

method: 滑动窗口

只需要判断在当前位置i的前面k个元素中，是否有一个元素落在[nums[i]-t, nums[i]+t]范围里面就行

保存前面k个元素用滑动窗口，因为后面需要查找窗口内的元素，所以窗口内的元素最好是有序的，所以使用set

先用lower_bound找大于等于nums[i]-t的最小值，再判断该值是否小于等于nums[i]+t

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
    set<long> st;
    for (int i = 0; i < nums.size(); i++) {
        auto it = st.lower_bound((long)nums[i] - t);
        if (it != st.end() && *it <= (long)nums[i] + t) return true;
        st.insert(nums[i]);
        if (i >= k) {   // 超过k个需要弹出最前面的元素
            st.erase(nums[i - k]);
        }
    }
    return false;
}