要求
给定一个整形数组，返回相加等于某一值的2个元素的下标。只要找到1对就行，但是数组中同一个元素不能使用2次，找不着就返回空数组。
示例
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
public class Main {
public static void main(String[] args) {
// write your code here
int[] sourceArray = {3,3};
int[] resultArray = TwoSum.twoSum1(sourceArray,6);
System.out.print("[");
for (int counter = 0;counter < resultArray.length;counter++) {
System.out.print(resultArray[counter]);
if (counter % 2 == 0)System.out.print(",");
}
System.out.println("]");
}
}
public class TwoSum {
/**
* 本方法只适合数组中没有重复元素的情况。
* 因为数组中没有重复元素
* 所以可以空间换时间
* 依据计数排序法的思想进行实现
* 这种方法挺浪费空间的
* 不过速度是真快
* 就是把值当成键来索引原来的下标。
* @param sourceArray
* @param targetValue
*/
static public void twoSum0(int[] sourceArray,int targetValue) {
int arrayLength = sourceArray.length;
int minValue = sourceArray[0];
int maxValue = sourceArray[0];
for (int element:sourceArray) {
if (element > maxValue)maxValue = element;
if (element < minValue)minValue = element;
}
int tempArrayLength = maxValue - minValue + 1;
//把源数组中的元素按照从小打到
// 的顺序放到tempArray，不过
// 需要加上偏移量，因为最小值
// 往往不从0开始，而是从大于0
// 的某个数开始。这主要是方便
// 索引，减少时间消耗。它能根
// 据源数组中的值索引该值在源
// 数组中的下标。
int[] tempArray = new int[tempArrayLength];
for (int counter = 0;counter < tempArrayLength;counter++)
tempArray[counter] = -1;
for (int counter = 0;counter < arrayLength;counter++)
tempArray[sourceArray[counter] - minValue] = counter;
boolean hasFind = false;
for (int counter = 0;counter < arrayLength;counter++) {
//因为源数组中是没有重复元素的，
// 所以一旦找到配对的元素，
// 那个元素就不再会被用到于是可
// 以舍弃。而这个被舍弃的元素对
// 应的另一半也不会被用到，相当
// 于被抠掉了。
if (sourceArray[counter] < minValue)continue;
int differenceValue = targetValue - sourceArray[counter];
//对应的那个值必须是源数组中的一个，这就必须满足它确实存在的条件
// ，而要满足这一条件，它就
// 1、不能越界。
// 2、它对应的下标确实存在。
// 3、它不能是自己。
if (differenceValue - minValue >= 0 &&
differenceValue - minValue < tempArrayLength &&
tempArray[differenceValue - minValue] != -1 &&
tempArray[differenceValue - minValue] != counter) {
hasFind = true;
sourceArray[tempArray[differenceValue - minValue]] = minValue - 1;
System.out.println("(" + tempArray[sourceArray[counter] - minValue] + "," + tempArray[differenceValue - minValue] + ")");
}
}
if (!hasFind)System.out.println("没有");
}
/**
* 这是数组中可能存在重复元素，并且只要找到就返回的做法，没找着就返回null。
* 于是思路就很简单了，直接遍历就行了。
* @param sourceArray
* @param targetValue
* @return
*/
static public int[] twoSum1(int[] sourceArray,int targetValue) {
for (int counter = 0;counter < sourceArray.length - 1;counter++) {
int component = targetValue - sourceArray[counter];
for (int counter0 = counter + 1;counter0 < sourceArray.length;counter0++) {
if (sourceArray[counter0] == component)
return new int[]{counter,counter0};
}
}
return new int[]{};
}
}