题目
给定一个整型数组，是否能找出其中的两个数使其和为某个指定的值？（假定是无序数组）
解法一：暴力破解（穷举法，不提倡）
/**
* 给定一个整型数组，是否能找出其中的两个数使其和为某个指定的值？（假定是无序数组）
* 暴力破解 (穷举，时间复杂度：O(n^2)，正常不会用这个，假如只是为了快速解题，对时间没有限制，用这个最简单)
*
* @param nums 无序整形数组
* @param target 和值
*/
public static void search1(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 search2(int[] nums, int target) {
System.out.println("二分查找(两个指针二分查找，时间复杂度：O(nlog(n)))");
// 1.排列（用的是Dual-Pivot Quicksort(快速排序),时间复杂度为O(nlog(n))）
// ****此处是重点****
Arrays.sort(nums);
// 2.类二分查找
int left = 0;
int right = nums.length - 1;
// for(;left < right;)
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
System.out.println("one:" + nums[left] + " two:" + nums[right]);
return;
}
if (sum < target) {// 太小 left增加
left++;
}
if (sum > target) {// 太大 right减少
right--;
}
}
System.out.println("找不到这两个数");
}
解法三：使用哈希表和辅助空间
/**
* 使用辅助空间(使用哈希表，时间复杂度是O(n),空间复杂度：O(n),n是数组大小)
* 把数值作为 key，它的下标作为 value 遍历数组，判断 map 是否含有这个目标值-当前数值， 有直接返回，没有的话放到map里面
*
* 所以以后写代码，如果有双层 for 循环，首先考虑一下能否用 map 替换一层
*
* 空间换时间的方式，用hashmap来记录值和index，这样只要遍历一遍，并用Hashmap直接判定是否存在另一个下标。
* 这种方法有一个问题，就是当存在相同值时，并且恰好求和的两个数是同值不同位时，必然会出问题。修正方式是
* hashmap中的value用list或者set来存储，那么如果最终两个值对应的index set不同，或者index set相同但set
* size>1，那么就是存在。
*/
public static void search3(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
System.out.println("one:" + nums[i] + " two:" + (target - nums[i]));
return;
}
map.put(nums[i], i);
}
System.out.println("找不到这两个数");
}
拓展题目
设计一个类，包含如下两个成员函数（允许整数集合中存在相同值的元素）：
save(int input) 插入一个整数到一个整数集合里。 test(int target) 检查是否存在两个数和为输入值。如果存在着两个数，则返回true，否则返回false
import java.util.HashMap;
import java.util.Iterator;
/**
* 设计一个类，包含如下两个成员函数（允许整数集合中存在相同值的元素）：
* save(int input) 插入一个整数到一个整数集合里。
* test(int target) 检查是否存在两个数和为输入值。如果存在着两个数，则返回true，否则返回false
*
* @author kongshubin
*
*/
public class TwoNumberOfSum {
// 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;
if (map.containsKey(two)) {
System.out.println("one:" + one + " two:" + two);
if (!(target == two << 1 && map.get(two) == 1)) {
// 如果target为two的2倍，并且只有一个two不同时成立，返回true
return true;
}
}
}
return false;
}
public static void main(String[] args) {
TwoNumberOfSum t = new TwoNumberOfSum();
t.save(5);
t.save(10);
t.save(4);
t.save(7);
System.out.println(t.test(12));
}
}
