一，问题描述

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

思路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
    
      intSets = new HashSet
     
      (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
    
      map=new HashMap
     
      ();        for(int i=0;i
     
    

 

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

for(int i=0;i

 

整合代码最终如下

/**     * 使用辅助空间(使用哈希表，时间复杂度是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
     
       map=new HashMap
      
       ();        // 1.扫描一遍数组，加入哈希表，时间复杂度是O(n)        for(int i=0;i
      
     
    

 

思考：假如数组中有重复的话，那么上面的将失效，因为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

允许整数集合中存在相同值的元素

分析：

与不同，这里需要算出的是存不存在这两个数，可以在上一篇的基础上修改一下，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
    
      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
    
      map = new HashMap
     
      ();    /**     * 插入一个整数到一个整数集合里     * @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
      
        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时，不断地重复上面的操作即可。