两数和问题（在数组中找出两数和为给定整数的两元素）-蒲公英云

两数和问题（在数组中找出两数和为给定整数的两元素）

题目：输入包含n个整数是数组A的整数x,求出满足A[i]+A[j]=x的i和j，如果没有这样的元素和，则返回-1和-1。

我的分析如下：

此题需要注意的是：数组中可能有重复元素，满足条件的解不止一组。

例如，给定数组A[1,3,2,2]和x=4,则满足条件的解为

（0，1）：1+3=4 和（2，3）：2+2=4。

解法一：暴力解法

遍历每个元素A[i]，并查找是否存在一个值等于x-A[i]的目标元素。

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70

测试用例和运行结果：

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70 1

解法二：先排序+指针+HashMap

先将给定的数组排序，再创建两个指针(i,j)，一个从头结点往后指i++，一个从尾节点向前指j—；

分以下三种情况：

int i = 0, j = A.length;
      while(i < j) {
          if(A[i]+A[j] < x) 
             i++;
          else if(A[i]+A[j] > x) 
             j--;
          else
             System.out.print("find out!");
    }

但是这样会数组因为重新排序而使索引混乱，因此在排序前可以将原数组元素及其索引存入哈希表中，用指针将元素查找出来后再通过哈希表将原索引取出来。

时间复杂度分析，存取哈希表是O(n),排序是O(nlog(n)),指针查找是O(n),一共大约是O(2n+nlog(n))。

解法三：哈希表

hm:将数组中的元素和索引以<键，值>的形式存储在哈希表hm中，（从两次遍历哈希表逐渐优化成一次遍历哈希表）

（一）首先想到的是两次遍历哈希表：f(n)=2n
     \*第一次是将数组中的每个元素和其索引以键值对形式存储在哈希表中
     \*第二次是依次遍历每个元素A\[i\]，看x-A\[i\]是否是哈希表中的某个键，若存在，则该键值即为索引。
但此种情况存在的问题是：因为遍历会将解输出两次，例如出现（1，2）和（2，1）这种情况。

（二）可以将上述两次遍历哈希表变成一次遍历f(n)=n，即在将数组元素a[i]加入哈希表之前先判断x-a[i]是否已经在当前的哈希表中，然后再加入，这样就不会出现重复输出解了。
 \* 哈希表用空间换取了时间，空间复杂度为O(n)，时间复杂度为O(n)
 \* 缺点：哈希表中不允许有重复的键，故此算法无法解决数组中有相同元素的情况。