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 > ) {
Set<Integer> set = new HashSet<>(nums.length);
for(int i = ; 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;
}
}