菜鸡又来问 leetcode 题目了

[lqw3030]

请教大家个问题 这题：

这个是排行前几的解法

public boolean containsDuplicate(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
                    for (int j = i - 1; j >= 0; j--) {
                        if (nums[i] > nums[j]) {
                            break;
                        } else if (nums[i] == nums[j]) {
                            return true;
                        }
                    }

                }
                return false;
    }

有没有朋友给我讲解下这么写的思路，这种解法如果输入

int[] nums = {88, 9, 88, 1, 88, 5, 88, 3, 88 };

不是返回的就不正确了吗？还是我没理解题目

[northisland]

肯定不对，举个简单的反例就可证明。
{3, 1, 3}

有高手解答么？
我只能想到排序后，从前往后遍历，
或者可穷举时用桶排序，桶>2 立即停止。

[cheniousl]

解法没问题啊，你不明白的点在哪？
你的例子里，外层第二次循环，i=2 的 88 就和内层第二次循环 i=0 的 88 重复，直接 false 了

[cheniousl]

哦，重复返回的是 true

[maninfog]

这个解法明显有问题嘛，就你举的这个例子就通不过，这种题我就只想用 hashset 哈哈哈

[Biwood]

这函数写的莫名其妙，为啥要写个 if (nums[i] > nums[j])，直接等于号返回 true，末尾返回 false 不就完了吗。
用了两层遍历，复杂度为 n²，应该还能优化。

[lqw3030]

@Biwood 这题的最快速度解法就是这个，我就是不理解，而且用我举例的那个数组跑就不通过

[lqw3030]

@maninfog 哈哈哈，我第一个想法也是 hashSet

[sunnyadamm]

双层嵌套，遍历数组有无与第一层相等值，有就直接返回 true，然后终止循环。否则开始第二次循环。很简单的逻辑，当然还有其他方法解答

[lqw3030]

@northisland 我在答案里看到这种解法，Arrays.sort 然后 for 一次，就是不理解我发的这个解法，而且前三个好像都这个思路

[mainlong]

我想了一个解法，大家看看有没有问题。

Python 有个类型是集合 set，把数组作为参数传给集合，再对比数组元素个数和集合元素个数就行了。不同说明有重复被删掉了。

[sunnyadamm]

楼主意思是 9 比 88 小，代码写的是 nums[i] > nums[j]，这里有疑问吗？代码在 if 里面，9 比 88 小这种情况不符合 if 和 elseif 的条件，if 及 elif 语句不执行，for 循环继续呀，没毛病。

[Xs0ul]

如果 int 范围有限，而数组很长（接近 int 总数量），就直接 bitmap

如果数组相对短，就自己做一个简单的 hashset，比如除 1000 取余数，1000 这个数的大小取决于 int 范围和数组长度

如果数组特别短，可以直接排序或者二叉搜索树

甚至可以先扫一遍了解数据分布

每种方法的优缺点，空间时间复杂度都可以和面试官讨论

[SingeeKing]

我第一反应：return len(nums) == len(set(nums))

[hzwjz]

@SingeeKing 简单优雅。

[hzwjz]

还有一种 nlogn 的解法就是数组排序后二分查找。

再有一种就是去重，然后返回去重后的新数组，接着比长度。

以上这两种本质上都依赖于双指针。

[binux]

因为数据弱？

[WildCat]

@Biwood 哇，这个 n^2 怎么打印出来的？

[lqw3030]

@sunnyadamm，重复输出 true，然而照他这样的算法输出了 false，和预期不一致

[KgM4gLtF0shViDH3]

@lqw3030 #6 最快的解法肯定不是这个，我到公司看看，双层 for 循环太慢了

[ingin]

@SingeeKing 很明显你错喽

[renyijiu]

感觉这个解法是数组排序了，自己想法空间换时间，用 hash 存值判断存在

[KgM4gLtF0shViDH3]

试了下用 go 字典插入判断耗时 28ms

[ColinWang]

位图法，O(n)的时间复杂度

[Biwood]

@WildCat PC 版搜狗输入法，输入“ pingfang ”就有二次方的上标了

[MisakaTang]

就是测试用例太弱被卡过去了,不加 break 是 LTE 但是那组数据是顺序的,加了这个 break 卡掉了这组数据,应该是这样

[SingeeKing]

@ingin #20 哪里错了。。。

[ingin]

@SingeeKing ==换成！=

[SingeeKing]

@ingin #27 额。。这就尴尬了

[Tidycc]

不是很懂那个 `nums[i] > nums[j]` 的用法，又不是有序数组。感觉还是使用 HashSet，看长度是否变短。