土豆丝不辣

[算法题]数组中查找两个数之和等于目标值

数组中查找两个数之和等于目标值:
给一个数组a={1,3,4,5,6,7,8}和一个target=9值，找到数组中两数和等于目标target值的两个整数，
并返回他们在原数组中的下标 [0,6] or [2,3]

O(n*n) 最低复杂度是O(n)

降低到O(n)->使用hashMap解决
target-arr[i] 是否出现
hashKey = target-arr[i],
最终结果是 arr[i] 和 target-arr[i] 在数组中出现的索引index
hashValue=数组的index值.

/**
 * 时间复杂度 O(n)+O(n)=O(n)
 * 空间复杂度 O(n)
 *
 * @param numbers 数组
 * @param target  目标值
 * @return in[]两数在数组中的原位置
 */
public static int[] twoArraySum(int[] numbers, int target) {
    HashMap<Integer, Integer> resultMap = new HashMap<>();
    for (int i = 0; i < numbers.length; i++) {
        resultMap.put(numbers[i], i);
    }

    for (int i = 0; i < numbers.length; i++) {
        int complement = target - numbers[i];
        if (resultMap.containsKey(complement) && resultMap.get(complement) != i) {
            return new int[]{resultMap.get(complement), i};
        }
    }
    return null;
}

/**
 * 一次遍历就返回两数之和
 *
 * @param numbers 数组
 * @param target  目标值
 * @return in[]两数在数组中的原位置
 */
public static int[] twoArraySumOneTime(int[] numbers, int target) {
    HashMap<Integer, Integer> resultMap = new HashMap<>();
    for (int i = 0; i < numbers.length; i++) {
        resultMap.put(numbers[i], i);
        int complement = target - numbers[i];
        if (resultMap.containsKey(complement) && resultMap.get(complement) != i) {
            return new int[]{resultMap.get(complement), i};
        }
    }
    return null;
}

public static void main(String[] args) {
    int[] arr = {1, 3, 4, 5, 6, 7, 8};
    int target = 11;
    int[] ints1 = twoArraySum(arr, target);
    System.out.println("ints1:" + Arrays.toString(ints1));

    int[] ints2 = twoArraySumOneTime(arr, target);
    System.out.println("ints2:" + Arrays.toString(ints2));
}
--------------------------------------------------------------------------
//ints1:[6, 1]
//ints2:[3, 4]

本文共计 2391 字，感谢您的耐心浏览与评论。