Contains Duplicate

Leetcode

Contains Duplicate

Question

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.

Analysis

利用hash表，将数组中的元素逐个插入hash表中，当遇到第一个重复不可插入的时候返回false，否则返回true

Code

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

Summary

一开始很蠢的先查看s内是否contain再插入，这样的话会报exceed time limits的错误，所以直接看是否能add即可

Contains Duplicate II

Question

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.

Analysis

由于java中的set中没有脚标，故没有办法进行脚标的对比，所以选择hash中的map对脚标进行记录

Code

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

Contains Duplicate III

Question

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.

Analysis

维持一个长度为k的窗口，每次检查新加入的值与窗口内其他的值是否差值有小于等于t的。但是如果嵌套的两个for循环，则会超时。利用Java中的Treeset、subSet查看是否有处于范围大小内的记录即可，复杂度为 O(n logk)

Code

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        SortedSet<Long> set=new TreeSet<Long>();
        int size=nums.length;
        if(size==0||size<2||k<1||t<0)
        // k<1而非k<0，eg：(1，0) k=0 t=1 k为0会一直移除当前的数字
            return false;
        for(int i=0;i<size;i++){
            SortedSet<Long> subset=set.subSet((long)nums[i]-t,(long)nums[i]+t+1);
            if(!subset.isEmpty())
                return true;
            
            if(i>=k){
              //必须有=，因为下一次循环的时候直接是从第i+1个开始比较；若不删除第i-k个，则此时即使间隔为k+1，也会有比较；eg：(1,3,1) k=1 t=1
                set.remove((long)nums[i-k]);
            }
            set.add((long)nums[i]);
        }
        return false;
    }
}

TreeSet/SubSet

TreeSet

TreeSet是集合，是用来存数据的，就像数组一样，但TreeSet是动态的。
TreeSet存的数据是无序号的，你不能通过get的方法获得里面的数据。
TreeSet存数据是有顺序的，这个顺序是你规定的，规定方法就是通过实现Comparator接口.

SubSet

Code

package com.java2novice.treeset;

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

public class MySetSublist {

	public static void main(String a[]){
		
		TreeSet<String> ts = new TreeSet<String>(new MyStrComp());
		ts.add("RED");
		ts.add("ORANGE");
		ts.add("BLUE");
		ts.add("GREEN");
		ts.add("WHITE");
		ts.add("BROWN");
		ts.add("YELLOW");
		ts.add("BLACK");
		System.out.println(ts);
		Set<String> subSet = ts.subSet("GREEN", "WHITE");
		System.out.println("sub set: "+subSet);
		subSet = ts.subSet("GREEN", true, "WHITE", true);
		System.out.println("sub set: "+subSet);
		subSet = ts.subSet("GREEN", false, "WHITE", true);
		System.out.println("sub set: "+subSet);
	}
}

class MyStrComp implements Comparator<String>{

	@Override
	public int compare(String str1, String str2) {
		return str1.compareTo(str2);
	}
	
}

Output

[BLACK, BLUE, BROWN, GREEN, ORANGE, RED, WHITE, YELLOW]
sub set: [GREEN, ORANGE, RED]
sub set: [GREEN, ORANGE, RED, WHITE]
sub set: [ORANGE, RED, WHITE]

Code

import java.util.SortedSet;
import java.util.TreeSet;
public class TreeSetDemo05{
    public static void main(String[] args){
        SortedSet<String> allSet = new TreeSet<String>();    
        allSet.add("A");
        allSet.add("B");
        allSet.add("C");
        allSet.add("D");
        allSet.add("E");
        System.out.println("第一个元素："+allSet.first());
        System.out.println("最后一个元素"+allSet.last());
        System.out.println("headSet元素"+allSet.headSet("C"));
        System.out.println("tailSet元素"+allSet.tailSet("C"));
        System.out.println("subSet元素:"+allSet.subSet("B","D"));
    }
}

Output

第一个元素：A
最后一个元素E
headSet元素[A, B]
tailSet元素[C, D, E]
subSet元素:[B, C]