题目-来自编程之美
给定一个数组，快速从其中找出两个数满足其之和等于给定的数，这里假设其中至少存在一组符合要求的解；
分析
这里的关键在于快速
- 最为愚钝的方式当然是：穷举，从数组中任意取出两个数字进行判断，但是时间复杂度为
;
- 一般是数组，首先进行排序，采用时间复杂度为
, 然后通过一次遍历求出所需的解，时间复杂度为
， 所以整个时间复杂度为
- 书中分析： 令
i = 0, j = n - 1, 查看arr[i] + arr[j]是否等于sum，如果是则结束，否则判断大小，如果小于sum，则i++,否则j--, 这样从两端向中间移动，则一定会找到的。 - 同时我借助快排思想中移动，上面每次只移动一个位置，能不能一次移动多个，这样在两个目标数距离比较近时，能过更加快速的找到。详见代码！事实证明可行！
- 书中分析： 令
实现(java)
package com.jiajia.find;
/**
* @ClassName: FindTowNum
* @Author: fanjiajia
* @Date: 2019/3/7 下午7:28
* @Version: 1.0
* @Description: 在一个序列中快速查找两个满足条件的两个数
*/
public class FindTowNum {
public static void main(String[] args) {
int[] arr = {2,3,9,5,7,8,4,6};
function(arr, 14);
}
private static void function(int[] arr, int targetNum) {
// 先排序（从小到大）
quickSort(arr, 0, arr.length - 1);
// 方法1：每次只移动一个下标
boolean flag = false; // 方法1是否寻找到
for (int i = 0, j = arr.length - 1; i < j; ){
if (arr[i] + arr[j] == targetNum){
System.out.println("方法1->存在两个数，分别为:" + arr[i] + "," + arr[j]);
flag = true;
break;
}else if (arr[i] + arr[j] < targetNum){
i++;
}else {
j--;
}
}
if (!flag){
System.out.println("不存在");
}
// 方法2
int i = 0, j = arr.length - 1;
while (i < j && (arr[i] + arr[j] != targetNum)) { // i 和 j不可能重合
while (arr[i] + arr[j] < targetNum && i < j) { // 移动i
i++;
}
while (arr[i] + arr[j] > targetNum && i < j) { // 移动j
j--;
}
}
if (i < j){
System.out.println("方法2->存在两个数，分别为:" + arr[i] + "," + arr[j]);
}else {
System.out.println("不存在");
}
}
/**
* 快排
* @param arr
* @param left
* @param right
*/
private static void quickSort(int[] arr, int left, int right){
if (left >= right) { // 必须加
return;
}
int temp = arr[left]; // 以左边的元素为基准元素
int i = left, j = right; // i,j为两个游标
while (i < j) {
while (i < j && arr[j] >= temp){ // 右边先走
j--;
}
while (i < j && arr[i] <= temp) {
i++;
}
if (i < j) {
swap(arr, i, j);
}
}
arr[left] = arr[i]; // 注意，这一步必须要，填上最左边的坑
arr[i] = temp; // 基准元素就位
quickSort(arr, left, i - 1); // 递归操作左边部分
quickSort(arr, i + 1, right); // 递归操作右边部分
}
/**
* 交换两个元素
* @param arr
* @param i
* @param j
*/
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
最后
此致，敬礼！
