Given an integer array withevenlength, where different numbers in this array represent differentkindsof candies. Each number means one candy of the corresponding kind. You need to distribute these candiesequallyin number to brother and sister. Return the maximum number ofkindsof candies the sister could gain.

Example 1:

Input:
 candies = [1,1,2,2,3,3]

Output:
 3

Explanation:

There are three different kinds of candies (1, 2 and 3), and two candies for each kind.
Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too. 
The sister has three different kinds of candies.

Example 2:

Input:
 candies = [1,1,2,3]

Output:
 2

Explanation:
 For example, the sister has candies [2,3] and the brother has candies [1,1]. 
The sister has two different kinds of candies, the brother has only one kind of candies.

Note:

1. The length of the given array is in range [2, 10,000], and will be even.
2. The number in given array is in range [-100,000, 100,000]

public class Solution {
    public int distributeCandies(int[] candies) {
        List<Integer> kinds = new ArrayList<Integer>();
        for(int i=0; i<candies.length; i++){
            int kind = candies[i];
            if(!kinds.contains(kind)){
                kinds.add(kind);
            }
        }
        return Math.min(kinds.size(),candies.length/2);
    }
}

提交之后提示：Submission Result:Time Limit Exceeded

将ArrayList修改为HashSet后运行成功

ArrayList的优缺点

从上面的几个过程总结一下ArrayList的优缺点。ArrayList的优点如下：

1、ArrayList底层以数组实现，是一种随机访问模式，再加上它实现了RandomAccess接口，因此查找也就是get的时候非常快

2、ArrayList在顺序添加一个元素的时候非常方便，只是往数组里面添加了一个元素而已

不过ArrayList的缺点也十分明显：

1、删除元素的时候，涉及到一次元素复制，如果要复制的元素很多，那么就会比较耗费性能

2、插入元素的时候，涉及到一次元素复制，如果要复制的元素很多，那么就会比较耗费性能

因此，ArrayList比较适合顺序添加、随机访问的场景。

容器：Set, List, Map ,数组。只有这四种容器。

Collection（集合） 一个一个往里装，Map 一对一对往里装。

Set:没有顺序，不可以重复。 List:有顺序，可以重复。 互相的equals就算重复。

Map定义了存储Key-Value的方法。

HashMap:HashMap实现了Map接口，底层使用的是Hash算法存储数据。HashMap将数据以键值对的方式存储。

HashSet:HashSet实现了Set接口，底层也是用的是Hash算法存储数据。而且HashSet内部有HashMap类型的成员变量,方法也调用了HashMap的方法，存储的时候只不过值为null.

ArrayList:ArrayList实现了List接口，底层使用的是数组，存储空间上是相邻的，所以查询起来会很方便，效率也会比LinkedList要高

LinkedList:实现了List接口，底层使用的是使用双向链表的形式，存储的数据在空间上很可能不相邻，但是他们都有一个引用连在一起，所以增删起来会很方便

Vector与ArrayList十分相似，区别就是就是vector是一种线程安全类,它的方法都带有Synchronized关键字,实际中很少用到。如果遇到多线程的问题，JAVA提供了一个Collections工具类，可以把ArrayList转换成线程安全的类。

当插入数据比较多的时候需要扩容，这一步很耗性能，在该题目中主要就是插入操作，所以采用Set

public class Solution {
    public int distributeCandies(int[] candies) {
        Set<Integer> kinds = new HashSet<Integer>();
        for(int i=0; i<candies.length; i++){
            int kind = candies[i];
            //if(!kinds.contains(kind)){
                kinds.add(kind);
            //}
        }
        return Math.min(kinds.size(),candies.length/2);
    }
}