Leetcode[217, 219, 220]Contains Duplicate

###Task1 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.

###Python ####O(n)

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        appear = set()
        for num in nums:
            if num in appear:
                return True
            appear.add(num)
        return False
        

###Java

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return false;
        }
        // better, O(n)
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i: nums) {
            if (set.contains(i)) {
                return true;
            }
            set.add(i);
        }
        
        return false;
    }
}

###Task2 Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

###Java

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length <= 1) {
            return false;
        }
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], i);
            } else {
                int pos = map.get(nums[i]);
                if (i - pos <= k) {
                    return true;
                }
                map.put(nums[i], i);
            }
        }
        
        return false;
    }
}

###Python class Solution(object): def containsNearbyDuplicate(self, nums, k): “”” :type nums: List[int] :type k: int :rtype: bool “”” map = {} for i, num in enumerate(nums): if num not in map: map[num] = i else: cur = map[num] if i - cur <= k: return True map[num] = i return False

###Task3
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

###Java
```java
public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length == 0 || t < 0 || k < 1) {
            return false;
        }
        
        TreeSet<Long> set = new TreeSet<Long>();
        for (int i = 0; i < nums.length; i++) {
            long left = (long)nums[i] - t;
            long right = (long)nums[i] + t + 1;
            SortedSet<Long> subset = set.subSet(left, right);
            if (!subset.isEmpty()) {
                return true;
            }
            if (i >= k) {
                set.remove((long)nums[i - k]);
            }
            set.add((long)nums[i]);
        }
        
        return false;
    }
}

###Points

• when finding the same number –> set/dict

  参考LeetCode Discuss：https://leetcode.com/discuss/38177/java-o-n-lg-k-solution TreeSet数据结构（Java）使用红黑树实现，是平衡二叉树的一种。 该数据结构支持如下操作：

  1. floor()方法返set中≤给定元素的最大元素；如果不存在这样的元素，则返回 null。
  2. ceiling()方法返回set中≥给定元素的最小元素；如果不存在这样的元素，则返回 null。