某数之和系列 (一)

Posted by Lain on 09-19,2019

没事做做算法题,给脑子开开光,走起。

1、两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

方法一 暴力枚举法

设两个嵌套的循环,内循环依次和外循环的值相加,判断是否等于目标值。由于过于暴力,代码就不放了。
时间复杂度:O(n2)

方法二 一遍哈希表

HashMap可以通过key值,在O(1)的时间复杂度下找到对应的value,原因是在添加元素的时候,HashMap会根据key的hash值,计算其在数组容器中对应的下标,并在将元素存放在那个地方,如果出现hash碰撞的情况,会在该坐标处构建链表,hash冲突越多,HashMap读写元素的时间复杂度越趋近O(n),这里我们只是简单的阐述一下HashMap是个什么,之后会写一篇HashMap的源码分析。

那么如何通过hash表来更快速的解决我们的问题呢?既然我们知道目标值Target,在已知一个数i的情况下,只要用Target-i就能得到预期的数,接下来只要判断该数是否在HashMap里就行了。

    public static void main(String[] args) {
        int[] nums = new int[]{2, 7, 11, 15};
        System.out.println(Arrays.toString(addTwo(nums,17)));
    }
    private static int[] addTwo(int[] nums,int target){
	//以数为key,以数组下标为value的HashMap
        HashMap<Integer,Integer> map = new HashMap();
        for(int i = 0;i<nums.length;i++){
            int c = target - nums[i];//计算差值
            if(map.containsKey(c)){//如果与该数相等的key存在
                return new int[]{map.get(c),i};//返回key对应的value,即数组下标
            }
            map.put(nums[i],i);//无事发生,将数与下标存入HashMap
        }
        return null;
    }

该算法时间复杂度为O(n) 空间复杂度也是O(n)

提交时间提交结果执行用时内存消耗语言
1 小时前通过3 ms37.4 MBJava

2、三数之和

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

这里采用指针法,核心思想是先按大小进行排序,然后固定最小值a,此时a在数组的最左边,假设其下标为k,然后用两个指针i和j分别指向k之后的数组区间,通过判断三数之和与0之间的关系,移动i和j的指针,使两者相互靠拢,直到两者相遇,则结束循环,向下一位移动k,进行新的判断。
我们先不处理重复的情况,这样有助于理解其基本思路:


    public static void main(String[] args) {
        int[] integer = new int[]{-1, 0, 1, 2, -1, -4};
        System.out.println(threeSum1(integer));
    }

    public static List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        for(int k = 0;k<nums.length - 2;k++){//最左值k,k只会位移到length-3的位置
            //如果最左边的数字大于0,则绝不可能出现相加为0的组合,结束程序
            if(nums[0]>0){return list;}
            //记录找值区间
            int i = k + 1;
            int j = nums.length - 1;
            while(i < j){
                int sum = nums[k] + nums[i] + nums[j];//计算和
                //如果相加之和小于0,则将i向右移动
                if(sum < 0) i++;//跳过重复
                if (sum == 0) {//如果相加之和等于0,则正中下怀,加入结果集,并同时向右向左移位
                    list.add(Arrays.asList(nums[k],nums[i],nums[j]));
                    j--;i++;//移位
                };
                if(sum >0)j--;//如果相加之和大于0,则将j向左移动
            }
        }
        return list;
    }

输出结果:[[-1, -1, 2], [-1, 0, 1], [-1, 0, 1]]
可以看到,这里是有重复的结果的,原因在于如果数组中有重复的元素,只要在k,i,j三个指针的中任意一个的位移过程中碰上了,就会出现重复的结果,因此我们要借助排序的优势,在指针位移的过程中跳过重复的数,以达到去重的效果

    public static List<Integer[]> threeAdd(Integer[] params){
        List<Integer[]> list = new ArrayList<>();
        Arrays.sort(params);
        System.out.println(Arrays.toString(params));
        for(int k = 0;k<params.length - 2;k++){//固定最左值k
            //如果最左边的数字大于0,则绝不可能出现相加为0的组合,结束程序
            if(params[0]>0){return list;}
            if(k>0 && params[k]==params[k-1])continue;
            //记录找值区间
            int i = k + 1;
            int j = params.length - 1;
            while(i < j){
                int sum = params[k] + params[i] + params[j];//计算和
                //如果相加之和小于0,则将i向右移动
                if(sum < 0) while (i < j&&params[i] == params[++i]);//跳过重复
                if (sum == 0) {//如果相加之和等于0,则正中下怀,加入结果集,并同时向右向左移位
                    list.add(new Integer[]{params[k],params[i],params[j]});
                    while (i<j && params[j] == params[--j]);//跳过重复,并向左移动j
                    while (i<j && params[i] == params[++i]);//跳过重复,并向右移动i
                };
                if(sum >0)while (i<j&&params[j] == params[--j]);
                //如果相加之和大于0,则将j向左移动
            }
        }
        return list;
    }

执行结果:
[[-1, -1, 2], [-1, 0, 1]]

提交时间提交结果执行用时内存消耗语言
几秒前通过55 ms47.3 MBJava