找出总和为一个整数的不同整数对的数量

Question

我正在尝试计算数组中对的数量，以便每对给出一个整数的总和！

我使用了以下代码：

     public static int SumPairs(Integer []input, int k){
    Map<Integer, Integer> pairs = new HashMap<Integer, Integer>();
    int tmp=0;
    //System.out.println(pairs.toString());
     for(int i=0;i<input.length;i++){
     if(pairs.containsKey(input[i])){
            System.out.println(pairs.containsKey(input[i]));
             System.out.println(input[i] +", "+ pairs.get(input[i]));
             input[i]=0;
            tmp++;

        }

        else
            pairs.put(k-input[i], input[i]);
    }return tmp;
}

问题是 ;例如，当我的阵列是 1 2 2 2 3 4 4 4 和 sum = 5 它计算如下

(4,1)
(4,1)
(4,1)
(3,2)

我想防止该方法多次使用一个数字！！所以输出将是

(4,1)
(3,2)

原文由 raghad Alamri 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

我使用存储值及其频率的地图：

 public static int SumPairs(Integer[] input, int k){
    Map<Integer, Integer> frequencies = new HashMap<>();
    int pairsCount = 0;

    for(int i=0; i<input.length; i++){
        int value = input[i];
        int complement = k - input[i];

        if(frequencies.containsKey(complement)){
            int freq = frequencies.get(complement) - 1;
            pairsCount++;
            //System.out.println(value + ", " + complement);
            if(freq == 0){
                frequencies.remove(complement);
            }else{
                frequencies.put(complement, freq);
            }
        }else{
            if(frequencies.containsKey(value)){
                frequencies.put(value, frequencies.get(value) + 1);
            }else{
                frequencies.put(value, 1);
            }
        }
    }
    return pairsCount;
}

原文由 Calculator 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

我希望这可以帮助

def numberOfPairs(a, k):

    # Let's do a o(n) approach by maintaining all the compliments of the K in a
    # visited set

    compliments = set()
    result = set()
    for v in a:
        # See if the element is in the compliments set, if so thats the pair
        if v in compliments:
            result.add((v, k-v))
        # If the element is not found in visited save the compliment of it in the visited set
        else:
            compliments.add(k-v)


    return len(result)

原文由 Prithiviraj Damodaran 发布，翻译遵循 CC BY-SA 4.0 许可协议