LeetCode-217

Contains Duplicate

Total Accepted: 20833 Total Submissions: 57794

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.

Java实现

第一种不好的方法：

最先想到的方法是两个嵌套循环来逐一判断:

public static 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;
    }

但是Submit的后，发现Status: Time Limit Exceeded

暴力测试没有通过，该算法是O(N*N)，所以得重新考虑，由于没有对Java的容器类的有一定的了解，没有立刻想到通过使用容器类的特性来解决问题。

第二种使用容器类方法：

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> hm=new HashSet<Integer>();
        if (nums.length==0) {
            return false;
        }
        int size=nums.length;
        for (int i = 0; i < size; i++) {
            if (!hm.contains(nums[i])) {
                hm.add(nums[i]);
            }
            else {
                return true;
            }
        }
        return false;
    }
}

有关Set结论

1. 存入Set每个元素必须是唯一的，不能有重复的元素。HashSet实现了Set接口，它不允许集合中有重复的值，在进行存储时，先进行判断，使用contain方法即可，复杂度与时间消耗就随之降下来了。
2. HashSet :为快速查找而设计的Set,存入HashSet的元素必须定义hashcode()（没有其他选择，这时默认的选择）
3. HashSet和HashMap的区别

C++实现

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        int len=nums.size();
        for(int i=1; i<len; i++){
            if(nums[i-1]==nums[i]){
                return true;
            }
        }
        return false;
    }
};