java - 给定一个目标总和，找出给定数组中是否有一对元素总和等于它

Question

import java.util.HashMap;

public class target 
{
    public static void hash(int []a,int sum)
    {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

        int i;

        for (i = 0; i < a.length; ++i) 
            map.put(a[i], sum-a[i]);

        for (i = 0; i < a.length; ++i) 
            if(map.containsValue(a[i]) && map.get(a[i])!=null)
             {
                System.out.println("("+a[i]+","+map.get(a[i])+")");
                map.remove(a[i]);
             }
    }

public static void main(String[] args)
{
    int []a={1, 2, 13, 34, 9, 3, 23, 45, 8, 7, 8, 3, 2};
    hash(a,11);
}
}

我想知道是否有比上述解决方案更好、更有效的解决方案。这个的复杂度是n。我可以做得更好吗？

Answer 1

您的实现遗漏了重复的对。

---

你可以

1. 对数组进行排序

2. 从头开始遍历每个元素

   • 计算所需的补数(和-元素)

   • 进行反向二分搜索(从排序数组的末尾开始)寻找该精确值

   • 如果找到，将两者都删除

归结为观察到的元素排序:

 n1 < n2 < n3 < n4 < n5 < n6

最有可能的对是对称地从两端到中间。现在，最坏的情况仍然很糟糕，但至少你没有哈希表开销