文章目录
前言一、题目描述二、思路1.暴力破解2.空间换时间（有点像桶排序思想）3，排序总结前言
本系列文章为leetCode刷题笔记，仅供参考。
一、题目描述
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例 1:
输入: [1,2,3,1]
输出: true
示例 2:
输入: [1,2,3,4]
输出: false
示例 3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
见：https://leetcode-/problems/contains-duplicate/
二、思路
1.暴力破解
对该数组遍历，依次判断是否有无重复元素，时间复杂度为O(n2),空间复杂度为O(1)。（Fail）
代码如下：
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])return true;}return false;}}
2.空间换时间（有点像桶排序思想）
采用一个临时数组来标记原数组中元素出现次数，但是没有考虑到有负整数的存在，时间复杂度为O(n)，空间复杂度为O(m)。（Fail)
代码如下：
public boolean containsDuplicate(int[] nums){int maxN=Integer.MIN_VALUE;for(int i=0;i<nums.length;i++){if(nums[i]>maxN)maxN=nums[i];}int[] tmp=new int[maxN+1]; //要想后面的maxN下标可用，申请空间需大于maxN。for(int i=0;i<nums.length;i++){tmp[nums[i]]+=1;if(tmp[nums[i]]==2)return true;}return false;}
3，排序
先排序（ologn），再判断是否存在重复元素。时间复杂度为O(nlogn)，空间复杂度为O(logn)，这里取得是递归调用栈的深度，（Pass)
代码如下：
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;}
总结
假设空间复杂度不做限制，且不采用排序，是否有时间复杂度低于O(n2)的解法呢？
如果觉得《LeetCode算法题1：判断整数数组是否存在重复元素》对你有帮助，请点赞、收藏，并留下你的观点哦！
