[算法学习]给定一个整型数组，找出两个整数为指定整数的和(2)

算法

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

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

理一理代码思路

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

1
2
3
4
5
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为数组大小）：

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
    }
}

整合代码最终如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 使用辅助空间(使用哈希表，时间复杂度是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>>来解决。