算法复健-第十天

Array-Easy-存在重复元素

题面

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

示例 1：

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

输出：true

解释：

元素 1 在下标 0 和 3 出现。

示例 2：

输入：nums = [1,2,3,4]

输出：false

解释：

所有元素都不同。

示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]

输出：true

提示：

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

解答过程

本题直接哈希表就行

代码

bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> set;
        for (size_t i = 0; i < nums.size(); i++)
        {
            if (set.find(nums[i]) != set.end())
            {
                return true;
            }

            set.insert(nums[i]);
        }
        return false;
    }

Array-Easy-存在重复元素II

题面

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• 0 <= k <= 10^5

解答过程

本题也用哈希表，但要注意，如果第一次找到不同的索引但是没有符合小于k的条件，就要把较前的那个值删去，因为后面仍然可能有满足条件的解

代码

bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> map;
        for (size_t i = 0; i < nums.size(); i++)
        {
            auto iter = map.find(nums[i]); 
            if (iter != map.end())
            {
                if (myabs(iter->second - i) <= k)
                {
                    return true;
                }
                else{
                    map.erase(iter);
                }
            }
            map.emplace(nums[i],i);
        }
        return false;
    }