算法练习·两数之和

算法练习·两数之和

题目

在一个整数数组array中,查找2个数字,要求这2个数字之和等于target

示例:

  • 存在数组array:[2, 5, 8, 5]
  • 目标值target:10
  • 2 + 8 ==> array[0] + array[2] = 10
  • 返回数组 [0,2]

解法一:暴力遍历法 O(n2)

    public static Integer[] testTowSum(){

        Integer[] arrays = {2, 5, 0, 2};
        int target = 7;

        for (int i = 0; i < arrays.length; i++) {
            for (int j = 0; j < arrays.length; j++) {
                if(arrays[i] + arrays[j] == target){
                    return new Integer[]{i,j};
                }
            }
        }
        return null;
    }

这个算法很简单,2层for循环遍历即可

解法二:哈希遍历法 O(n)

  • 本题就好比在解答二元一次方程x + y = target。已知target,假设知道x的情况下。那么y = target - x。在循环数组的过程中,可以看做 x 已知,那么只需要判断 y 是存在于数组中即可
  • 将数组中的所有元素存储在HashMap中,通过containsKey来判断 y 是否存在。
  • jdk7以前HashMap底层是hash表和链表的方式实现的,所以,这个方法在hash碰撞比较严重的时候,时间复杂度最大为:O(n2), 最低:O(n)
  • jdk8以后,HashMap使用hash + RBtree实现,意味着时间复杂度最大为:O(logn) 最低为:O(n)
    public static Integer[] testTowSum(){

        Integer[] arrays = {2, 5, 0, 2};
        int target = 7;

        HashMap<Integer,Integer> indexMap = new HashMap<>();
        //生成HashMap索引
        for (int i = 0; i < arrays.length; i++) {
            indexMap.put(arrays[i],i);
        }
        //循环数组
        int y;
        for (int i = 0; i < arrays.length; i++) {
            y = target - arrays[i];
            if(indexMap.containsKey(y)){
                return new Integer[]{i,indexMap.get(y)};
            }
        }
        return null;
    }
# 算法  java 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×