LeetCode_排序_简单_217.存在重复元素

今天药忘吃喽~ 2023-10-06 18:48 56阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个整数数组，判断是否存在重复元素。  
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false。

**示例 1：**  
输入: \[1,2,3,1\]  
输出: true

**示例 2：**  
输入: \[1,2,3,4\]  
输出: false

**示例 3：**  
输入: \[1,1,1,3,3,4,3,2,4,2\]  
输出: true

**提示：**  
1 <= nums.length <= 105  
\-109 <= nums\[i\] <= 109

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/contains-duplicate

## 2.思路 ##

（1）哈希表  
① 设置布尔变量 flag，初始值为 false，即开始时认为数组 nums 中不存在重复元素；  
② 遍历数组 nums，对于当前元素 nums\[i\]，如果该元素已经存在于哈希表 hashMap 中，则说明存在重复的元素，令 flag = true 并退出遍历；否则将键值对 (nums\[i\], i) 添加到 hashMap 中；  
③ 数组遍历结束或退出后返回 flag 即可。

（2）排序  
先对数组 nums 进行排序，然后再遍历该数组，每次判断相邻的两个元素是否相等，如果相等则说明存在重复的元素。

相似题目：  
[LeetCode\_滑动窗口\_简单\_219. 存在重复元素 II][LeetCode_219. _ II]  
[LeetCode\_滑动窗口\_中等\_220.存在重复元素III][LeetCode_220._III]

## 3.代码实现（Java） ##

//思路1————哈希表
    public boolean containsDuplicate(int[] nums) {
        
        boolean flag = false;
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
        
            if (hashMap.containsKey(nums[i])) {
        
                flag = true;
                break;
            } else {
        
                hashMap.put(nums[i], i);
            }
        }
        return flag;
    }

//思路2————排序
    public boolean containsDuplicate(int[] nums) {
        
        //对数组 nums 进行升序排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
        
            if (nums[i] == nums[i + 1]) {
        
                return true;
            }
        }
        return false;
    }

[LeetCode_219. _ II]: https://blog.csdn.net/weixin_43004044/article/details/125702235
[LeetCode_220._III]: https://blog.csdn.net/weixin_43004044/article/details/119317656