地址
难度
简单
题目
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例 1：
输入：nums = [1,2,3,1]
输出：true
示例 2：
输入：nums = [1,2,3,4]
输出：false
示例 3：
输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true
提示：
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
思路
- 暴力破解
双重 for 循环。判断是否存在相同的值，存在则返回 true，否则返回 false。
时间复杂度 O(n^2)，空间复杂度 O(1)。不过在 Leetcode 上执行的时候。提示超时时间限制
class Solution {
public boolean containsDuplicate(int[] nums) {
for(int i = 0;i< nums.length-1;i++){
for(int j = i+1;j< nums.length;j++){
if(nums[i] == nums[j]){
return true;
}
}
}
return false;
}
}
- 排序
题目要求是判断存在重复的元素，那么将数组从小到大进行排序。然后再一次 for 循环，判断相邻的两个数是否有相同的。
其时间复杂度为O(n*log(n))，空间复杂度为 O(1)
class Solution {
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;
}
}
- 计数法
利用 HashMap，其中 key 为数值，value 为出现次数。遍历整个数组，对记录每个数值出现的次数()。接着遍历 HashMap 中的每个 Entry，寻找 value 值大于 1 的 。
其时间复杂度为 O(n)，空间复杂度为 O(n)
class Solution {
public boolean containsDuplicate(int[] nums) {
HashMap<Integer,Integer> map =new HashMap<>();
for(int x:nums){
map.put(x,map.getOrDefault(x,0)+1);
}
for (int x : map.values()){
if(x >1){
return true;
}
}
return false;
}
- 使用 set
遍历数组，数字放到 set 中。如果数字已经存在于 set 中，直接返回 true。如果成功遍历完数组，则表示没有重复元素，返回 false。
其时间复杂度为 O(n)，空间复杂度为 O(n)
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num: nums) {
if (set.contains(num)) {
return true;
}
set.add(num);
}
return false;
}
}