leetcode——[217]ContainsDuplicate存在重复

题目

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

如果任何值在数组中出现至少两次，函数应该返回 true。如果每个元素都不相同，则返回 false。

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

解题方法

联系之前的从排序数组中删除重复项，可以现将数组进行排序，然后用一个循环遍历进行判断是否存在重复元素。我们需要考虑的是对于传递过来的数组，是否需要保证其不变，如果需要则将原数组进行复制之后再进行排序判断，否则直接对原数组进行操作。这里为了追求速度，直接对原数组进行操作，时间复杂度为O(nlogn)，跑了5ms，超过了98.62%的java提交。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                return true;
            }
        }
        return false;
    }
}

结语

做这道题我马上联想到了之前刷过的题，切身体会到积累的收获，编程也是这样，我相信通过不断的练习，我也能达到大师的水平。无论是《刻意练习：如何从新手到大师》，还是10000小时定律，核心思想都是坚持！Keep coding！

2018.4.19更新

经一位朋友提醒，需要指出还有一种时间复杂度、空间复杂度均为O(n)的方法。可以利用HashSet不能包含重复元素的特性来解决这道题。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> hashset=new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            hashset.add(nums[i]);
        }
        return set.size() != nums.length;
    }
}