Plain's Blog

休想打败我的生活🔥

LeetCode(217)之存在重复元素(Contains Duplicate)

Plain's Avatar 2019-02-08 LeetCode

  1. 1. 题目描述(官方原文)
    1. 1.1. 示例 1:
    2. 1.2. 示例 2:
    3. 1.3. 示例 3:
  2. 2. 思路
  3. 3. 代码实现(Java)
  4. 4. 复杂度

题目链接:https://leetcode-cn.com/problems/contains-duplicate/

题目描述(官方原文)

给定一个整数数组,判断是否存在重复元素。

如果任何值在数组中出现至少两次,函数返回 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

思路

可以通过Set来存储遍历过的值,如果当前值存在于Set中,就说明有重复元素,返回true,反之就添加到Set中,继续遍历,直到遍历结束。

代码实现(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Test {
public static boolean containsDuplicate(int[] nums) {
Set<Integer> setNums = new HashSet<>();

for (int i = 0; i < nums.length; i ++){
if (setNums.contains(nums[i])){
return true;
} else {
setNums.add(nums[i]);
}
}

return false;

}

public static void main(String [] args){
int [] nums = {1,1,2,3,4};

System.out.println("result: " + containsDuplicate(nums));

}

}

复杂度

  • 时间复杂度:O(n)

  • 空间复杂度:O(n)

本文作者 : Plain
This blog is under a CC BY-NC-SA 3.0 Unported License
本文链接 : https://plain-dev.com/leetcode-contains-duplicate/

本文最后更新于 天前,文中所描述的信息可能已发生改变