在数组中查找目标和的对

Question

首先，关于这类问题似乎有很多问题，但我找不到对我有帮助的问题。

我正在尝试找到具有 O(n) 或线性时间复杂度的目标对。

int[] input = {1, 6, 3, 2, 5, 5, 7, 8, 4, 8, 2, 5, 9, 9, 1};
int target = 10;

预期输出（任意顺序）：

(1,9)(1,9)(6,4)(3,7)(2,8)(2,8)(5,5)(5,5)(5,5)(8,2)(8,2)(9,1)(9,1)

我已经尝试过使用两个 for 循环的暴力破解方法，它给了我正确的输出但是 O(n*n)。

for (int i = 0; i < input.length; i++) {
    for (int j = i + 1; j < input.length; j++) {
        if (input[i] + input[j] == target) {
            System.out.println("(" + input[i] + "," + input[j] + ")");
        }
    }
}

然后我尝试了不给出所有对的散列。缺少两对

Set<Integer> set = new HashSet<>();
for (int num : input) {
    set.add(num);
    if (set.contains(target - num)) {
        System.out.println("(" + (target - num) + "," + num + ")");
    }
}

输出：

(5,5)(5,5)(3,7)(2,8)(6,4)(2,8)(8,2)(5,5)(1,9)(1,9)(9,1)

我尝试了其他方法，结果比预期的要多

Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < input.length; i++) {
    map.put(input[i], i);
}

for (int num : input) {
    if (map.containsKey((target - num))) {
        System.out.println("(" + num + "," + (target - num) + ")");
    }
}

输出：

(1,9)(6,4)(3,7)(2,8)(5,5)(5,5)(7,3)(8,2)(4,6)(8,2)(2,8)(5,5)(9,1)(9,1)(1,9)

Answer 1

出现 HashMap 的问题是因为您在开头添加了所有数组元素，因此多次查找值和目标。
例如：当当前地图元素num为6时，我们在地图中找到了一对4（10-6）
同样，当 num 为 4 时，我们再次找到一对，因为地图中有 6 (10-4)。
因此，为了获得正确的计数和配对，我们需要同时检查和添加数字。
这是使用 HashMap.

的 O(N) 实现

class Solution
{
    static int getPairsCount(int[] arr, int n, int target)
    {
        HashMap<Integer,Integer> map = new HashMap<>();
        int pairs=0;
        for (int i=0; i<n; i++)
        {
            if (map.containsKey(target - arr[i]))
            {
                pairs += map.get(target - arr[i]);
                for (int j=1; j<=map.get(target - arr[i]); j++)
                    System.out.print("(" + (target-arr[i]) + "," + arr[i] + ") ");
            }
            map.put(arr[i] , map.getOrDefault(arr[i],0)+1);
        }
        return pairs;
    }
    public static void main (String [] args)
    {
        int[] input = {1, 6, 3, 2, 5, 5, 7, 8, 4, 8, 2, 5, 9, 9, 1};
        int target = 10;
        System.out.println(getPairsCount(input , input.length , target));
    }
}

输出： 13（双）

(5,5) (3,7) (2,8) (6,4) (2,8) (8,2) (8,2) (5,5) (5,5) (1,9) (1,9) (9,1) (9,1)

您的 HashSet 方法的问题在于它删除了重复值，因此您得到的结果不正确。

在数组中查找目标和的对

Find pairs for a target sum in an array

java

arrays

sum

pairwise