找出数组中两数之和为指定值的所有整数对

原创
2016/11/28 09:44
阅读数 1.7K

一,问题描述

给定一个整型数组(数组中的元素可重复),以及一个指定的值。打印出数组中两数之和为指定值的 所有整数对

思路1:可以用hash表来存储数组中的元素,这样我们取得一个数后,去判断sum - val 在不在数组中,如果在数组中,则找到了一对二元组,它们的和为sum,该算法的缺点就是需要用到一个hash表,增加了空间复杂度。

思路2:同样是基于查找,我们可以先将数组排序,然后依次取一个数后,在数组中用二分查找,查找sum -val是否存在,如果存在,则找到了一对二元组,它们的和为sum,该方法与上面的方法相比,虽然不用实现一个hash表,也没不需要过多的空间,但是时间多了很多。排序需要O(nLogn),二分查找需要(Logn),查找n次,所以时间复杂度为O(nLogn)。

思路3:该方法基于第2种思路,但是进行了优化,在时间复杂度和空间复杂度是一种折中,但是算法的简单直观、易于理解。首先将数组排序,然后用两个指向数组的指针,一个从前往后扫描,一个从后往前扫描,记为first和last,如果 fist + last < sum 则将fist向前移动,如果fist + last > sum,则last向后移动。

二,算法分析

一共有两种方法来求解。方法一借助排序,方法二采用HashSet

方法一:

先将整型数组排序,排序之后定义两个指针left和right。left指向已排序数组中的第一个元素,right指向已排序数组中的最后一个元素

将 arr[left]+arr[right]与 给定的元素比较,若前者大,right--;若前者小,left++;若相等,则找到了一对整数之和为指定值的元素。

此方法采用了排序,排序的时间复杂度为O(NlogN),排序之后扫描整个数组求和比较的时间复杂度为O(N)。故总的时间复杂度为O(NlogN)。空间复杂度为O(1)

 

方法二:

依次遍历整型数组,对整型数组中的每一个元素,求解它的suplement(expectedSum-arr[i]).suplement就是指定的值减去该数组元素。

如果该元素的 suplement不在HashSet中,则将该元素添加到HashSet。

如果该元素的suplement在HashSet中,说明已经找到了一对整数之和为指定值的元素。

该方法使用了HashSet,故空间复杂度为O(N),由于只需要扫描一遍整型数组,故时间复杂度为O(N)

 

三,完整代码实现:

复制代码

import java.util.Arrays;
import java.util.HashSet;

public class ExpectSumOfTwoNumber {
    
    public static void expectSum_bySort(int[] arr, int expectSum)
    {
        if(arr == null || arr.length == 0)
            return;
        Arrays.sort(arr);
        int left = 0, right = arr.length - 1;
        
        while(left < right)
        {
            if(arr[left] + arr[right] > expectSum)
                right--;
            else if(arr[left] + arr[right] < expectSum)
                left++;
            else//equal
            {
                System.out.println(arr[left] + " + " + arr[right] + " = " + expectSum); 
                left++;
                right--;
            }
        }
    }
    
    
    public static void expectSum_bySet(int[] arr, int expectSum)
    {
        if(arr == null || arr.length == 0)
            return;
        HashSet<Integer> intSets = new HashSet<Integer>(arr.length);
        
        int suplement;
        for (int i : arr)
        {
            suplement = expectSum - i;
            if(!intSets.contains(suplement)){
                intSets.add(i);
            }else{
                System.out.println(i + " + " + suplement + " = " + expectSum);
            }
        }
    }
    
    //hapjin test
    public static void main(String[] args) {
        int[] arr = {2,7,4,9,3};
        int expectSum = 11;
        expectSum_bySet(arr, expectSum);
        System.out.println("************");
        expectSum_bySort(arr, expectSum);
        System.out.println("----------------");
        int[] arr2 = {3,7,9,1,2,8,5,6,10,5};
        int expectSum2 = 10;
        expectSum_bySet(arr2, expectSum2);
        System.out.println("**********");
        expectSum_bySort(arr2, expectSum2);
    }
}

 

问题描述:给定一个整型的数组,找出其中的两个数使其和未指定的值,返回两个数的数组下标(假定是无序数组,数组元素各不相同,要求时间复杂度为O(n),n为数组长度,可以使用辅助空间)

分析:时间复杂度是O(n),即是扫描一遍数组,不可嵌套扫描。必须全部数组扫描和查找全部,扫描+查找=O(n),可以使用数据结构哈希表,哈希表的查找的时间复杂度是O(1)。

理一理代码思路

(1). 因为输出是数组下标,那么就让数组下标为哈希表中的值,数组的值为哈希表中的键,扫描一遍数组,put进HashMap,代码如下(时间复杂度O(n),n为数组大小):

        HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
        for(int i=0;i<nums.length;i++)
        {
            map.put(nums[i], i);
        }

 

(2).第二遍扫描就是要查找出值,这里要做两个判断,一个就是两个结果数的值不能相同,这是题目要求的,还有一个就是判断HashMap是否有值,代码如下(最坏情况的时间复杂度是O(n),n为数组大小):

        for(int i=0;i<nums.length;i++)
        {
            // 得到第二个数的值
            int two=target-nums[i];
            // 如果存在第二个数的数组下标&&结果的两个数不是同一个数的值
            if(map.containsValue(two)&&target!=2*two)
            {
                result[0]=i;
                result[1]=map.get(two);
                // 返回找到的两个数的数组下标
                return result;
            }
        }

 

整合代码最终如下

    /**
     * 使用辅助空间(使用哈希表,时间复杂度是O(n),空间复杂度:O(n),n是数组大小)
     * @param nums
     * @param target
     * @return 没有找到的话数组中数值就是{-1,-1},否则找到,其实我想返回null的,但是觉得返回null不礼貌,因为null有毒
     */
    public static int[] findTwo3(int[] nums, int target)
    {
        // 结果数组
        int[] result={-1,-1};
        // 目标是数组下标,所以键值对为<数值,数值对应数组下标>,这里要说一下,哈希表的查找的时间复杂度是O(1)
        HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
        // 1.扫描一遍数组,加入哈希表,时间复杂度是O(n)
        for(int i=0;i<nums.length;i++)
        {
            map.put(nums[i], i);
        }
        // 2.第二次扫描,目标值-当前值,差值作为key,看看map里有木有,没有就下一个循环,直到数组扫描完毕或找到value,所以最坏情况的时间复杂度是O(n)
        for(int i=0;i<nums.length;i++)
        {
            // 得到第二个数的值
            int two=target-nums[i];
            // 如果存在第二个数的数组下标&&结果的两个数不是同一个数的值
            if(map.containsValue(two)&&target!=2*two)
            {
                result[0]=i;
                result[1]=map.get(two);
                // 返回找到的两个数的数组下标
                return result;
            }
        }
        // 没有找到
        return result;
    }


 

思考:假如数组中有重复的话,那么上面的算法将失效,因为数据结构HashMap<Interget,Interget>已经不合适,这样我觉得可以使用HashMap<Interget,List<Interget>>来解决。

问题描述:给定一个整型数组,是否能找出其中的两个数使其和为某个指定的值?(假定是无序数组)

解法一:暴力破解(穷举法,不提倡)

    /**
     * 暴力破解
     * (穷举,时间复杂度:O(n^2),正常是不会用这个滴,假如只是为了快速解题,对时间没有限制,用这个最简单)
     *
     * @param nums
     * @param target
     */
    public static void findTwo1(int[] nums, int target)
    {
        int one, two;
        for (int i = 0; i < nums.length; i++)
        {
            one = nums[i];
            two = target - one;
            for (int j = 0; j < nums.length; j++)
            {
                if (i != j)
                {
                    if (two == nums[j])
                    {
                        System.out.println("one:" + one + " two:" + two);
                        return;
                    }
                }
            }
        }
        System.out.println("找不到这两个数");
    }

 

解法二:二分法(相当于用两个指针)

    /**
     * 两个指针二分查找
     * (排序时间复杂度为O(nlog(n)),while最多O(N),所以最终程序的时间复杂度为:O(nlo(n)))
     *
     * @param nums
     * @param target
     */
    public static void findTwo2(int[] nums, int target)
    {
        // 1.排列(用的是Dual-Pivot Quicksort(快速排序),时间复杂度为O(nlog(n)))
        Arrays.sort(nums);
        // 2.类二分查找
        int left = 0;
        int right = nums.length - 1;
        while (left < right)
        {
            if (nums[left] + nums[right] > target)
            {// 太大 right减少
                right--;
            }
            else if (nums[left] + nums[right] < target)
            {// 太小left增加
                left++;
            }
            else
            {// 找到结果,结束查找
                System.out.println("one:" + nums[left] + " two:" + nums[right]);
                return;
            }
        }
        System.out.println("找不到这两个数");
    }

问题描述:
设计一个类,包含如下两个成员函数:
Save(int input) 插入一个整数到一个整数集合里。
Test(int target) 检查是否存在两个数和为输入值。如果存在着两个数,则返回true,否则返回false
允许整数集合中存在相同值的元素

分析:
[算法学习]给定一个整型数组,找出两个整数为指定整数的和(2)不同,这里需要算出的是存不存在这两个数,可以在上一篇的基础上修改一下数据结构,HashMap

理一理代码思路

(1). 写Save(int input)。这个就简单了,只需判断是否存在input为key,有就value+1,没有就value=1。代码如下:

public void Save(int input)
{
    int count = 0;
    if (map.containsKey(input))
    {
        count = map.get(input);
    }
    map.put(input, count + 1);
}

 

(2). 检查是否存在两个数和为输入值。上面的分析已经讲得差不多,这里就直接贴代码。代码如下:

public boolean Test(int target)
{
    Iterator<Integer> iterator = map.keySet().iterator();
    while (iterator.hasNext())
    {
        int one = iterator.next();
        int two = target - one;
        System.out.println("one:"+one+" two:"+two);
        if (map.containsKey(two))
        {
            // two<<1等价于two*2
            if (!(target ==two<<1 && map.get(two) == 1))
            {
                return true;
            }
        }
    }
return false;
}

 

整合代码最终如下

import java.util.HashMap;
import java.util.Iterator;

public class TwoNumOfSum3
{
    // key:数值,value:数值对应的个数
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

    /**
     * 插入一个整数到一个整数集合里
     * @param input
     */
    public void Save(int input)
    {
        int count = 0;
        if (map.containsKey(input))
        {
            count = map.get(input);
        }
        map.put(input, count + 1);
    }

    /**
     * 检查是否存在两个数和为输入值
     * @param target
     * @return 如果存在着两个数,则返回true,否则返回false
     */
    public boolean Test(int target)
    {
        Iterator<Integer> iterator = map.keySet().iterator();
        while (iterator.hasNext())
        {
            int one = iterator.next();
            int two = target - one;
            System.out.println("one:"+one+" two:"+two);
            if (map.containsKey(two))
            {
                if (!(target ==two<<1 && map.get(two) == 1))
                {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * @param args
     */
    public static void main(String[] args)
    {
        TwoNumOfSum3 t=new TwoNumOfSum3();
        t.Save(5);
        t.Save(10);
        t.Save(4);
        t.Save(7);
        System.out.println(t.Test(12));
    }
}

 

时间复杂度O(n)的解法

我们可以用一个哈希表或数组或bitmap(后两者要求数组中的整数非负)来保存sum-x的值, 这样我们就只需要遍历数组两次即可找到和为指定值的整数对。这种方法需要O(n) 的辅助空间。如果直接用数组或是bitmap来做,辅助空间的大小与数组中的最大整数相关, 常常导致大量空间浪费。比如原数组中有5个数:1亿,2亿,3亿,4亿,5亿。sum为5亿, 那么我们将bitmap中的sum-x位置1,即第4亿位,第3亿位,第2亿位,第1亿位,第0位置1. 而其它位置都浪费了。

如果使用哈希表,虽然不会有大量空间浪费,但要考虑冲突问题。

时间复杂度为O(nlogn)的解法

我们来考虑一种空间复杂度为O(1),而且实现也很简单的算法。首先,将数组排序。 比如排序后得到的数组a是:-2 -1 0 3 5 6 7 9 13 14。然后使用low和high 两个下标指向数组的首尾元素。如果a[low]+a[high] > sum,那么说明a[high] 和数组中的任何其它一个数的和都一定大于sum(因为它和最小的a[low]相加都大于sum)。 因此,a[high]不会与数组中任何一个数相加得到sum,于是我们可以直接不要它, 即让high向前移动一位。同样的,如果a[low]+a[high] < sum,那么说明a[low] 和数组中的任何其它一个数的和都一定小于sum(因为它和最大的a[high]相加都小于sum)。 因此,我们也可以直接不要它,让low向前移动一位。如果a[low]+a[high]等于sum, 则输出。当low小于high时,不断地重复上面的操作即可。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部