Two Sums

要求

给定一个整形数组，返回相加等于某一值的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[]{};
    }
}