题目链接🔗力扣（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;}elsebreak;}a[end+gap] = tmp;}}return ret;
}
bool containsDuplicate(int* nums, int numsSize)
{return ShellSort(nums,numsSize);
}