LeetCode算法笔记 217. 存在重复元素

给你一个整数数组 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 <= 105
-109 <= nums[i] <= 109

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/contains-duplicate

import junit.framework.TestCase;
import org.junit.Test;

import java.util.Arrays;
import java.util.HashSet;

public class LeetCode01 extends TestCase {

    /**
     * 时间复杂度：O(NlogN)，其中N为数组的长度。需要对数组进行排序。
     * 空间复杂度：O(logN)，其中N为数组的长度。注意我们在这里应当考虑递归调用栈的深度。
     */
    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(N)，其中N为数组的长度。
     * 空间复杂度：O(N)，其中N为数组的长度。
     */
    public boolean containsDuplicate2(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();
        for (int num : nums) {
            if (!hashSet.add(num)) {
                return true;
            }
        }
        return false;
    }


    @Test
    public void test01() {
        int[] arr1 = {1, 2, 3, 1};
        int[] arr2 = {1, 2, 3, 4};
        int[] arr3 = {1, 1, 1, 3, 3, 4, 3, 2, 4, 2};

        System.out.println(containsDuplicate(arr1));
        System.out.println(containsDuplicate(arr2));
        System.out.println(containsDuplicate(arr3));
        System.out.println("=====================");
        System.out.println(containsDuplicate2(arr1));
        System.out.println(containsDuplicate2(arr2));
        System.out.println(containsDuplicate2(arr3));
    }
}