349. Intersection of Two Arrays 是否重复

不重复的：

方法一

［一句话思路］：排序之后用归并。

［一刷］：

根据返回方法的类型来判断corner case。判断空、0数组的corner case还不一样，得分开写
由于先排序了，nums1[i] < nums2[j]时，i++可以继续在nums2[j]里找是否有相同的
index=0时肯定不会重复，一定要插入
写法是Arrays.sort(nums1)
定义int i还不够，要初始化为0
并列用几个if可能会越界，还是用else if吧
result定义的长度不能是temp.length=nums1,应该是index，实际统计了多少是多少
不直接返回temp[k]的原因：会有很多空

［二刷］：

没有定义int k就直接用了，注意要定义成为int型再用
while (i < nums1.length && j < nums2.length) 两个边界要同时满足才行

格式上：for循环, else 后面也要加花括号

［总结］：结果中有几个数要看index加到了多少

［复杂度］：sort n*logn, merge n／1

［英文数据结构］：Array sort, array merge

［其他解法］：下面

［题目变变变］：array merge（后插）

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        
        int[] zeroArray = new int[0];
        if (nums1.length == 0 || nums2.length == 0) {
          return zeroArray;
        }
        if (nums1 == null || nums2 == null) {
          return null;
        }
        
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        int i = 0;
        int j = 0;
        int index = 0;
        int []temp = new int[nums2.length];//大小随意，反正result的大小只和实际的index大小有关
        
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                if (index == 0 || temp[index - 1] != nums1[i]) {
                    temp[index++] = nums1[i]; 
                }
                i++;
                j++;
            } 
            else if (nums1[i] < nums2[j]) {
                i++;
            } 
            else {
                j++;
            }
            }//某一个数组到头了就不用管了，因为反正只需要比较相同的部分
        
        int []result = new int[index];
        for (int k = 0; k < index; k++) {
            result[k] = temp[k];
        }
        
        return result;
    }
}

View Code

方法二

［一句话思路］：用两个HashSet，不重复地插入，不重复地查找：错。把nums1全部插入，用hashset.contains查找就行了

［一刷］：

HashSet数据结构这样写
hash.size可以测量hash的长度，用来衡量result的尺寸
zeroArray的写法符合loweCamelCase
for (Integer num : resultHash)，打印resulthash中的全部。传到result时，还是要用index一个个地传（右边等于num）

for (Integer num : resulthash) {
            result[index++] = num;
        }

［总结］：注意表达方式：接口名＝new 类。此类为HashSet<Integer>，大小写间隔

［复杂度］：n/n

［英文数据结构］：hashset

［其他解法］：见下

［题目变变变］：

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        
        int[] zeroArray = new int[0];
        if (nums1.length == 0 || nums2.length == 0) {
            return zeroArray;
        }
        if (nums1 == null || nums2 == null) {
            return null;
        }
        
        HashSet<Integer> hash = new HashSet<>();
        for (int i = 0; i < nums1.length; i++) {
            hash.add(nums1[i]);
        }
        
        HashSet<Integer> resulthash = new HashSet<>();
        int j = 0;
        for (j = 0; j < nums2.length; j++) {
            if (hash.contains(nums2[j]) && !resulthash.contains(nums2[j])) {
                resulthash.add(nums2[j]);
            }
        }
        
        int size = resulthash.size();
        int[] result = new int[size];
        int index = 0;
        for (Integer num : resulthash) {
            result[index++] = num;
        }
        
        return result;
    }
}

View Code

方法三：

［一句话思路］：nums2有重复就添加一次，v减100直到小于零。

［一刷］：

临时结果不能用hashset来存，因为元素不能重复。临时结果用list。好处：能且只能用get put方法，不能用下标访问
方法写错了，hashset hashmap区别：

HashSet和HashMap的区别

HashMap	HashSet
HashMap实现了Map接口	HashSet实现了Set接口
HashMap储存键值对	HashSet仅仅存储对象
使用put()方法将元素放入map中	使用add()方法将元素放入set中
HashMap中使用键对象来计算hashcode值	HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false
HashMap比较快，因为是使用唯一的键来获取对象	HashSet较HashMap来说比较慢

［总结］：一定要每次－100后判断是否还>0，一一对应

［复杂度］：

||获取|查找|添加/删除|空间||
|ArrayList |O(1)| O(1)|O(N) | O(N)|
|LinkedList | O(N) | O(N) |O(1)|O(N)
|HashMap | O(N/Bucket_size)|O(N/Bucket_size)|O(N/Bucket_size)|O(N)

［英文数据结构］：

［其他解法］：

［题目变变变］：

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        for (int i = 0; i < nums1.length; i++) {
            if (!map.containsKey(nums1[i])) {
                map.put(nums1[i], 1);
            }
            else if (map.containsKey(nums1[i])) {
                map.put(nums1[i], map.get(nums1[i]) + 100);
            }
        }
        
        List<Integer> temp = new ArrayList<Integer>();
        
        for (int j = 0; j < nums2.length; j++) {
            if (map.containsKey(nums2[j]) && map.get(nums2[j]) > 0) {
                temp.add(nums2[j]);
                map.put(nums2[j], map.get(nums2[j]) - 100);
            }
        }
        
        int[] result = new int[temp.size()];
        for (int k = 0;k < temp.size(); k++) {
            result[k] = temp.get(k);
        }
        
        return result;
    }
}

View Code