Array Two

Come on,baby~

(1)Contains Duplicate

 有自己的思路：两个for双重循环直接一个个比较，但肯定不是最优解。所以，使用Set中的HashSet（一种没有重复元素的无序集合），最优解如下：

HashSet百度链接：http://baike.baidu.com/link?url=TmKKUevqDj_4IZT_b3bFPhJJRZdY4suUZB42Ybo-9xWtoVIMLQnNT39C_OteQlMiu6jC8stsg15EfHvt11Oz9a

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums != null && nums.length > 1) {
            Set<Integer> set = new HashSet<>(nums.length);
            for(int i : nums) {
                if (set.contains(i)) {
                    return true;
                }
                else {
                    set.add(i);
                }
            }
        }
        return false;
    }
}

set.contains() set.add()方法的使用

for (int i; nums)是一个foreach循环遍历，就是遍历nums这个数组中的所有值，每次把其中的一个值赋给i.

跟for (int i = 0; i < nums.length; i++) {...}效果相同。也即上述代码可改为：

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

【注意补充Java库中相关集合的知识--卷1P562】

第二天：忘记限制数组不为空而且数组的长度要大于1。  

(2)Contains Duplicate II

题目大意：给定一个整数数组nums与一个整数k，当且仅当存在两个不同的下标i和j满足nums[i] = nums[j]并且|i-j|<=k时返回true，否则返回false。 

解题思路：使用HashMap（一种存储键/值关联的数据结构），key存数组元素值，value存元素对应的索引，每来一个元素进行判断如果之前没有存过则存进去，如果之前有存则取出之前那个元素的索引值判断是否小于K,小于k返回true,不小于则存进去覆盖之前的那个【思路的重点】。

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

map.containsKey() map.get() map.put()方法的使用。【key存元素对应的索引，value存元素值为什么不对？？？】

！！！时间超限解法：在前一解法基础上进行修改，但是时间超限 

时间超限原因？？？

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

最早的情况考虑不周解法（估计时间也超限）:eg:[1,0,1,1]和1  output:false  expected:true

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