加上给定一个数组和值x。设计一个算法使得如果数组中存在两个元素的和为x,则输出两个元素的值组成的数组(不区分先后),否则输出{-1, -1}。
分析:
private static int[] findSum(int[] arr, int sum) {
// STEP1: 先对数组采用归并排序进行排序
mergeSort(arr, 0, arr.length);
// STEP2: 遍历数组,用二分查找法查找是否存在sum-arr[i]的元素
for (int i=0; i<arr.length; i++) {
int j = binarySearch(arr, 0, arr.length, sum - arr[i]);
if (j != -1) {
if (j != i) {
return new int[] {arr[i], arr[j]};
} else {
// j = i的时候,则需要判断j的左侧和右侧的值是否和j相等,相等则证明存在两个元素
if (arr[j - 1] == arr[j]) {
return new int[] {arr[i], arr[j - 1]};
} else if (arr[j + 1] == arr[j]) {
return new int[] {arr[i], arr[j + 1]};
}
}
}
}
return new int[]{-1, -1};
}
注意其中的mergeSort和binarySearch调用的是前一章节所指的代码http://www.cnblogs.com/Kidezyq/p/8379267.html。
private static int[] findSumWithMap(int[] arr, int sum) {
Map<Integer, Integer> map = new HashMap<>();
// STEP1: 将数据入map
for (int i = 0; i < arr.length; i++) {
map.put(arr[i], i);
}
// STEP2: 开始判断sum-arr[i]是否在map中
for (int i = 0; i < arr.length; i++) {
// 因为遍历顺序同放入map的顺序都是从前到后,所以如果存在多个同值元素,其最终会将后者的下标放入map,此时不影响判断逻辑
if (map.get(sum - arr[i]) != null && i != map.get(sum - arr[i])) {
return new int[]{arr[i], sum - arr[i]};
}
}
return new int[]{-1, -1};
}
private static int[] findSumTwoSide(int[] arr, int sum) {
// STEP1: 使用归并排序对数组进行排序
mergeSort(arr, 0, arr.length);
// STEP2: 进行两端查找
int lowIndex = 0;
int upIndex = arr.length - 1;
while (upIndex > lowIndex) {
if (arr[lowIndex] + arr[upIndex] == sum) {
// 相等直接返回
return new int[] {arr[lowIndex], arr[upIndex]};
} else if (arr[lowIndex] + arr[upIndex] < sum) {
// 小于左侧右移
lowIndex++;
} else {
// 大于右侧左移
upIndex--;
}
}
return new int[] {-1, -1};
}
其解决思想就是分治了。将n个元素的规模依次降低,最终降到2个元素的和。这里给出三个元素求和的例子,其他多维依次类推:
private static int[] findSumOf3Digits(int[] arr, int sum) {
// STEP1:先调用归并排序算法进行排序
mergeSort(arr, 0, arr.length);
// STEP2: 进行细化问题处理
// 先申请一个数组来存储排除一个元素后的数组元素组成的新的数组
int[] leftArr = new int[arr.length - 1];
for (int i = 0; i < arr.length; i++) {
// 复制arr[i]左侧元素到数组起始位置
if (i > 0) {
System.arraycopy(arr, 0, leftArr, 0, i);
}
// 复制arr[i]右侧元素到数组结尾位置
if (i < arr.length - 1) {
System.arraycopy(arr, i + 1, leftArr, i, arr.length - i - 1);
}
// 如果剩下两个数的和满足,则返回三个元素
int[] leftIndexes = findSumTwoSide(leftArr, sum - arr[i]);
if (!Arrays.equals(leftIndexes, new int[] {-1, -1})) {
return new int[] {arr[i], leftIndexes[0], leftIndexes[1]};
}
}
return new int[] {-1, -1, -1};
}