一个未排序的整数数组nums，它的大小numsSize是作为函数containsDuplicate的参数给出的，如果至少有一个重复值存在，我们必须返回一个布尔值true，否则为false。对于这个任务，我选择检查每个元素，以及之后的元素是否相等，直到到达最后一个元素，如果相等，我将返回true，否则返回false。
bool containsDuplicate(int* nums, int numsSize){
for(int i =0 ;i< numsSize-1;i++)
{
for(int j = i+1;j < numsSize; j++)
{
if(nums[i] == nums[j])
{
return true;
}
}
}
return false;
}
为了最小化运行时间，我只在发现重复项时编写返回值，但我的代码在大尺寸数组上仍然表现不佳，如果可能的话，我期望一个时间复杂度为O(n)的算法。我们是否可以跳过那些与之前的值重复的值呢?我已经看到了所有其他的解决方案，但我找不到一个更好的解决方案在c。
你的算法是O(n^2)。但是如果你先排序，这可以在不到O(n^2)的时间内完成，那么确定数组中是否有重复的是O(n)。
您可以维护一个查找表，以确定每个值是否以前见过，这将在O(n)时间内运行，但是除非数组中存储的值的潜在范围相对较小，否则这将占用大量内存。
例如，如果你知道数组中的值范围是0-127。
int contains_dupes(int *arr, size_t n) {
char seen[128] = {0};
for (size_t i = 0; i < n; i++) {
if (seen[arr[i]]) return 0;
seen[arr[i]] = 1;
}
return 1;
}
但是如果我们假设int是4字节，并且数组中的值可以是任何int，并且我们使用char作为查找表，那么您的查找表必须是4GB
O(n)时间，O(n)空间:使用集合或映射。解析数组，依次检查每个元素在set或map中的成员关系。如果它存在，那么你找到了一个副本;如果没有，则添加。
如果O(n)空间太昂贵，您可以通过使用布谷鸟散列进行第一次传递来获得更少的代价，布谷鸟散列是一种空间高效的数据结构，可以保证没有假阴性，但可能有假阳性。使用与上面相同的方法，但使用布谷鸟散列而不是集合或映射。您检测到的任何重复都可能是假阳性，因此需要进行检查。
然后，使用第一段中描述的方法第二次解析数组，但跳过任何不在候选集合中的内容。
这仍然是O(n)时间
https://en.wikipedia.org/wiki/Cuckoo_hashing