主页 / 问题 / 1365760
Accepted
alex_t
Asked:2022-05-25 15:43:45 +0800 CST2022-05-25 15:43:45 +0800 CST

调整算法

  • 772

任务：给定一个整数数组，您需要返回两个数字的索引，其和等于给定数字。我们可以假设数组只有一个解。您不能两次使用相同的号码。

Пример1: [2, 7, 11, 15], 9
Ответ: [0, 1]

Пример2: [3, 2, 4], 6
Ответ: [1, 2]

如果我们假设数组是有序的（这不是条件！），那么我使用两个指针的方法来解决它：

    public int[] twoSum(int[] nums, int target) {
        int l = 0, r = nums.length - 1;

        while (l < r) {
            int currentSum = nums[l] + nums[r];

            if (currentSum == target) {
                return new int[]{l, r};
            } else if (currentSum > target) {
                r--;
            } else if (currentSum < target) {
                l++;
            }
        }

        throw new RuntimeException("the pair is not found");
    }

O(n)复杂度。

但是第二个例子有问题：

Пример2: [3, 2, 4], 6
Ответ: [1, 2]

应该给1.2，我有一个异常崩溃。 告诉我如何在数组无序的情况下更正算法？

java

3 个回答

  1. 是的，没有办法解决。要么排序，要么使用另一种算法——在最简单的情况下，用二次时间的两个循环，或者使用哈希表，那么时间是线性的，但是内存是 O(n)

    • 3

  2. 如果不考虑排序，那么最简单的解决方案是不使用额外的数据结构，检查嵌套循环：

    public static int[] twoSum(final int target, int ... nums) {
    for (int i = 0, n = nums.length; i < n - 1; i++) {
        int a = nums[i];
        for (int j = i + 1; j < n; j++) {
            int b = nums[j];
            if (target == a + b) {
                return new int[]{i, j};
            }
        }
    }
    
    throw new RuntimeException("the pair is not found");
}

    是否可以使用哈希表的解决方案（如果输入数组包含重复项，则修复）：

    public static int[] twoSum(final int target, int ... nums) {
    System.out.println(Arrays.toString(nums));
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0, n = nums.length; i < n; i++) {
        int a = nums[i];
        int b = target - a;
        if (map.containsKey(a) && map.get(b) > -1) {
            return new int[]{map.get(b), i};
        }
        map.putIfAbsent(a, i); // запомнить меньший индекс
        map.computeIfAbsent(b, k -> -1);
        System.out.println("i=" + i + "; map=" + map);
    }
    
    throw new RuntimeException("the pair is not found");
}

    测试：

    System.out.println("результат 1: " + Arrays.toString(twoSum(6, 2, 2, 3, 5, 1)));
System.out.println("результат 2: " + Arrays.toString(twoSum(6, 2, 5, 2, 3, 4, 1)));

    [2, 2, 3, 5, 1]
i=0; map={2=0, 4=-1}
i=1; map={2=0, 4=-1}
i=2; map={2=0, 3=2, 4=-1}
i=3; map={1=-1, 2=0, 3=2, 4=-1, 5=3}
результат 1: [3, 4]
[2, 5, 2, 3, 4, 1]
i=0; map={2=0, 4=-1}
i=1; map={1=-1, 2=0, 4=-1, 5=1}
i=2; map={1=-1, 2=0, 4=-1, 5=1}
i=3; map={1=-1, 2=0, 3=3, 4=-1, 5=1}
результат 2: [0, 4]
    • 2
  3. Best Answer

    感谢HashMap提示！这是最终正确的决定（系统接受它）：

        public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            int key = target - nums[i];

            if (map.containsKey(key) && i != map.get(key)) {
                return new int[]{i, map.get(key)};
            }
        }

        throw new RuntimeException("the pair is not found");
    }
    • 0

相关问题