包含重复 - leetcode Java解决方案-DEV365 开发者社区

您好读者，让我们现在解决一个leetcode问题。

在此博客中，让我们解决Contains Duplicate是Blind 75 List of LeetCode Problems。

对于初学者来说，这是一个非常好的Leetcode简单问题。

这个问题有多种潜在解决方案，我们将在此博客中通过。

了解问题

问题的目的是确定数组是否包含任何重复值

在问题描述中，给出了：

给定数字数量：nums
返回true如果数组中有任何值至少出现两次
返回false如果数组中的所有值都是不同的

了解测试箱

为了更好地理解问题，给出了三个示例：

在示例1中，给出了：

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

在这里，我们可以在第一个也是最后一个索引上发现1两个，因此1是此数组中的重复值。因此，我们可以返回输出true。

在示例2中，给出了：

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

在这里，我们可以看到所有四个数字在此数组中都是不同的值。因此，我们可以返回输出false。

在示例3中，给出了：

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

在这里，我们可以在此数组中看到数字1,2,3和4的许多重复值。因此，我们可以返回输出true。

蛮力方法

蛮力方法将是将每个数字与数组中的其他每个数字进行比较，直到我们找到重复的数字为止。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        for(int i=0;i<nums.length; i++) {
            for(int j=i+1; j<nums.length; j++) {
                if(nums[i] == nums[j]) { 
                    // found the duplicate
                    return true;
                }
            }
        }
        return false;
    }
}

这是理解代码的关键点：

这种方法遵循一种蛮力的方法，将每个数字与数组中的其他每个数字进行比较以查找重复。
我们使用嵌套环通过数组中的所有可能的元素对穿越。
外循环在数组中的每个元素上迭代，内部环将该元素与其余元素进行比较。
如果发现任何两个元素相等，则意味着我们找到了重复的值，并且我们返回true。
比较了所有可能的对并找不到任何重复项后，我们返回false。

时间复杂性：

这种方法的时间复杂性为o（n^2），其中n是“ nums”数组中的元素数。这是因为我们已经嵌套循环，使我们在最坏情况下将每个元素与其他每个元素进行比较。

空间复杂性：

这种方法的空间复杂性是o（1），因为它不需要随着输入大小而生长的任何其他空间。

更好的方法：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i+1]) {
                return true;
            }
        }
        return false;
    }
}

这是理解代码的关键点：

此方法首先要对数组进行排序以简化重复的检查过程。
使用 Arrays.sort() 方法以升序排序该数组。
通过对数组进行排序，重复的元素彼此相邻，从而更容易通过比较相邻元素来识别重复。
我们遍历排序的数组，并将每个元素与其下一个相邻元素进行比较。
如果相邻元素相等，则意味着我们找到了重复的值，并且我们返回true。
如果在检查所有相邻对后找不到重复项，我们返回false。

时间复杂性：

这种方法的时间复杂性为o（n * log（n）），其中n是“ nums”数组中的元素数。这是因为对阵列进行排序需要O（n * log（n））时间，使用有效排序算法（如合并排序或快速排序）。

空间复杂性：

这种方法的空间复杂性是O（log（n）），其中n是“ nums”数组中的元素数。此空间用于排序算法中的递归调用。

Java解决方案（使用哈希集）：

我们可以使用标签来有效检查给定数组中的重复项。
Hashset是存储独特元素的数据结构。它允许恒定时间（O（1））操作，例如添加和搜索元素。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> dups = new HashSet<Integer>();
        for (int n : nums) {
            if (dups.contains(n)) {
                return true;
            }
            dups.add(n);
        }
        return false;
    }
}

这是理解代码的关键点：

我们遍历“ nums”数组，对于每个元素'n'，我们检查它是否已经存在于标签中。
如果存在该值，则意味着我们找到了重复，因此我们返回True。
如果不存在该值，我们将其添加到标签中以跟踪独特的元素。
遍历整个数组并没有找到任何重复项后，我们返回false。

时间复杂性：

该解决方案的时间复杂性是O（n），其中n是“ nums”数组中的元素数。这是因为我们一次穿越整个数组。

空间复杂性：

该解决方案的空间复杂性是O（n），其中n是“ nums”数组中的元素数。这是因为在最坏的情况下，数组中的所有元素都可以是唯一的，并存储在标签中。

java解决方案（使用哈希马普）：

我们可以使用hashmap在给定数组中有效检查重复项。
Hashmap是一个数据结构，该数据结构存储键值对，每个密钥都是唯一的。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashMap<Integer, Boolean> dups = new HashMap<>();        
        for (int n : nums) {
            if (dups.containsKey(n)) {
                return true;
            }            
            dups.put(n, true);
        }        
        return false;
    }
}

这是理解代码的关键点：

我们遍历“ nums'数组，对于每个元素'n'，我们检查它是否已经是哈希图中的键。
如果它是关键，则意味着我们找到了重复的值，因此我们返回True。
如果该元素不作为键，我们将其添加到具有“ true”值以跟踪其存在的值中。
遍历整个数组并没有找到任何重复项后，我们返回false。

时间复杂性：

该解决方案的时间复杂性是O（n），其中n是“ nums”数组中的元素数。这是因为我们一次穿越整个数组。

空间复杂性：

该解决方案的空间复杂性是O（n），其中n是“ nums”数组中的元素数。这是因为在最坏的情况下，数组中的所有元素都可以是唯一的，并将其作为键存储在哈希图中。

结论

蛮力解决方案具有O（n^2）的时间复杂性，但没有额外的内存使用。
对数组进行排序可以提高时间的复杂性（n * log（n）），但仍然不需要额外的内存。
使用hashmap＆Hashset提供了O（n）的最佳时间复杂性，但需要额外的内存。

NeetCode解决方案视频：

https://www.youtube.com/watch?v=3OamzN90kPg

建议学习数据结构和算法的资源

DS算法博客的基础知识：

Hashing in Java

推荐leetcode问题的YouTuber：

免费学习数据结构和算法的资源：

建议学习数据结构和算法的课程：

NeetCode Courses
ZTM：掌握编码访谈（BIG TECH）：可在Udemy和ZTM Academy上找到
ZTM：掌握编码访谈：可在Udemy和ZTM Academy上获得
Data Structures & Algorithms, Level-up for Coding Interviews Course
Striver’s A2Z (Free) Course

学习数据结构和算法的顶级Coursera课程：

（注意：可以审核Coursera课程以免费获得讲座）

ð披露：请注意，此页面上提到的某些链接可能是会员链接。这意味着，如果您单击以下链接之一并进行购买，我可能会从出售中获得一个小佣金。

我是谁？

我是一个软件工程书呆子Aswin Barath，他喜欢构建Web应用程序，现在在我自由职业生活生活的忙碌期间通过Blogging分享了我的知识。这是我所有我的疯狂的链接，由平台在一个地方分类为：https://linktr.ee/AswinBarath

继续学习

现在，我想这是我说再见。但是，嘿，您是时候开始学习。。您已经做到了这么好工作，谢谢阅读我的博客ð。