题目链接🔗力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
1. 题目分析
本题是要找到数组中的重复元素，所以我们分析出一下几点：
1. bool是一种数据类型，true是非0值，false是0.。
2. 数组中只要任意一个值出现两次及以上就返回true。
3. 数组中每个元素都不同，也就是每个元素只出现一次就返回false。
2. 做题思路
我们首先想到的就是遍历两次数组，但是需要注意的是时间复杂度是O(N^2)，我们这样写的代码是过不去的，因为当数组很大的时候，跑的会很慢，时间超过了限制。
所以我们在这里要放弃遍历的思想，那应该怎么解决呢？
作者想到的方法，利用希尔排序来解决问题，通过排序，找到相同的元素就返回1，如果当排序结束的时候还没有找到就返回0。下面就是代码啦！
2. 源代码
int ShellSort(int* a,int n) { int gap = n; int ret = 0; while(gap > 1) { gap = gap / 2; for (int i = 0; i < n-gap; ++i) { int end = i; int tmp = a[end+gap]; while(end >= 0) { if(a[end] > tmp) { a[end+gap] = a[end]; end = end - gap; } else if(a[end] == tmp) { ret = 1; return ret; } else break; } a[end+gap] = tmp; } } return ret; } bool containsDuplicate(int* nums, int numsSize) { return ShellSort(nums,numsSize); }
