写一个查找表和数组的算法

写一个查找表和数组的算法

查找有无一般使用set数据结构

查找对应关系使用Map映射数据结构

给定两个数组nums1=[1，2，2，1] num2=[2，2]求两个数组的公共元素 结果为[2]

将一个集合中的元素存入set集合中，然后从另一个集合中取出元素判断在不在原来的set集合中，如果在则存

入另一个set集合。

    public int[] intersection(int[] nums1, int[] nums2) {

        TreeSet record = new TreeSet();
        for(int num: nums1)
            record.add(num);

        TreeSet resultSet = new TreeSet();
        for(int num: nums2)
            if(record.contains(num))
                resultSet.add(num);

        int[] res = new int[resultSet.size()];
        int index = 0;
        for(Integer num: resultSet)
            res[index++] = num;

        return res;
    }

给定两个数组nums1=[1，2，2，1] num2=[2，2]求两个数组的交集 结果为[2，2]

与上一道题不同的地方在于记录每一个数组的元素也要记录出现的次数，次数也有意义，典型的键值对应的问题。

    public int[] intersect(int[] nums1, int[] nums2) {
        //HashMap record = new HashMap();
        TreeMap record = new TreeMap();
        for(int num: nums1)
            if(!record.containsKey(num))
                record.put(num, 1);
            else
                record.put(num, record.get(num) + 1);

        ArrayList result = new ArrayList();
        for(int num: nums2)
            if(record.containsKey(num) && record.get(num) > 0){
                result.add(num);
                record.put(num, record.get(num) - 1);
            }

        int[] ret = new int[result.size()];
        int index = 0;
        for(Integer num: result)
            ret[index++] = num;

        return ret;
    }

给定一个整形数组nums，返回两个索引值等于给定的target值

        HashMap record = new HashMap();
        for(int i = 0 ; i < nums.length; i ++){

            int complement = target - nums[i];
            if(record.containsKey(complement)){
                int[] res = {i, record.get(complement)};
                return res;
            }

            record.put(nums[i], i);
        }

        HashMap record = new HashMap();
        for(int i = 0 ; i < nums.length ; i ++)
            record.put(nums[i], i);

        for(int i = 0 ; i < nums.length; i ++){

            Integer index = record.get(target - nums[i]);
            if(index != null && index != i){
                int[] res = {i, index};
                return res;
            }
        }

给定四个整形数组A\B\C\D，A\B\C\D均含有相同的元素个数N，寻找多少个i,j,k,l的组合，使得A[i]+B[j]+C[k]+D[l] == 0，

和有可能重复，如果暴力解发n^4效率不够，可以降低复杂度为n^2

   public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {

        if(A == null || B == null || C == null || D == null)
            throw new IllegalArgumentException("Illegal argument");

        HashMap map = new HashMap();
        for(int i = 0 ; i < C.length ; i ++)
            for(int j = 0 ; j < D.length ; j ++){
                int sum = C[i] + D[j];
                if(map.containsKey(sum))
                    map.put(sum, map.get(sum) + 1);
                else
                    map.put(sum, 1);
            }

        int res = 0;
        for(int i = 0 ; i < A.length ; i ++)
            for(int j = 0 ; j < B.length ; j ++)
                if(map.containsKey(-A[i]-B[j]))
                    res += map.get(-A[i]-B[j]);

        return res;
    }

    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {

        if(A == null || B == null || C == null || D == null)
            throw new IllegalArgumentException("Illegal argument");

        HashMap mapAB = new HashMap();
        for(int i = 0 ; i < A.length ; i ++)
            for(int j = 0 ; j < B.length ; j ++){
                int sum = A[i] + B[j];
                if(mapAB.containsKey(sum))
                    mapAB.put(sum, mapAB.get(sum) + 1);
                else
                    mapAB.put(sum, 1);
            }

        HashMap mapCD = new HashMap();
        for(int i = 0 ; i < C.length ; i ++)
            for(int j = 0 ; j < D.length ; j ++){
                int sum = C[i] + D[j];
                if(mapCD.containsKey(sum))
                    mapCD.put(sum, mapCD.get(sum) + 1);
                else
                    mapCD.put(sum, 1);
            }

        int res = 0;
        for(Integer sumab: mapAB.keySet()){
            if(mapCD.containsKey(-sumab))
                res += mapAB.get(sumab) * mapCD.get(-sumab);
        }

        return res;
    }

给定平面上的n个点，存在多少条路径由这些点构成的三元组使得i，j两点的距离等于i，k两点的距离。‘

查找表的键是距离，值是有几个这样的点

    public int numberOfBoomerangs(int[][] points) {

        int res = 0;
        for( int i = 0 ; i < points.length ; i ++ ){

            // record中存储 点i 到所有其他点的距离出现的频次
            HashMap record = new HashMap();
            for(int j = 0 ; j < points.length ; j ++)
                if(j != i){
                    // 计算距离时不进行开根运算, 以保证精度
                    int dis = dis(points[i], points[j]);
                    if(record.containsKey(dis))
                        record.put(dis, record.get(dis) + 1);
                    else
                        record.put(dis, 1);
            }

            for(Integer dis: record.keySet())
                res += record.get(dis) * (record.get(dis) - 1);
        }

        return res;
    }

    private int dis(int[] pa, int pb[]){
        return (pa[0] - pb[0]) * (pa[0] - pb[0]) +
               (pa[1] - pb[1]) * (pa[1] - pb[1]);
    }

给定一个整形数组nums和一个整数k，是否存在索引i和j使得nums[i]==nums[j]，且i和j之间的差不超过k

滑动窗口思路，因为nums[i]-nums[j]