java 查找总和为整数的不同整数对的数量

Finding the number of distinct pairs of integers that sum up to an integer

提问by raghad Alamri

I am trying to count the numbers of pairs in an array such that each pair gives the sum of an integer!

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

I used the following code :

我使用了以下代码：

    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;
}

the problem is ; for example when my array is 1 2 2 2 3 4 4 4and sum = 5it compute as following

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

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

I want to prevent the method from using a number more than once !! so the output will be

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

(4,1)
(3,2)

回答by Calculator

I use a map storing values and their frequencies:

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

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;
}

回答by Prithiviraj Damodaran

I hope this can help

我希望这可以帮助

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 = []
    for v in a:
        # See if the element is in the compliments set, if so thats the pair
        if v in compliments:
            result.append((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)


    if len(result) == 1 or len(result) == 0:
        return len(result)

    # Now lets get the distinct pairs 

    result.sort()
    prev = result[0]
    distinct = []
    for r in result:
        if len(set(r) - set(prev)) > 0:
            distinct.append(prev)
            distinct.append(r)
        prev = r

    if len(distinct) == 0:
        return 1
    else:
        return  len(distinct)  

回答by prashant

This works for all the test cases I could think of. Please add in the comment section any test case that this code fails so that I can fix it. If it works, please accept the solution.

这适用于我能想到的所有测试用例。请在评论部分添加此代码失败的任何测试用例，以便我可以修复它。如果有效，请接受解决方案。

public class DistinctPairs {

    private static int count(int target, int... arr) {
        int count = 0;
        Set<String> seen = new HashSet<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            int k = target - arr[i];
            int[] pair = new int[]{k, arr[i]};
            Arrays.sort(pair);
            String s = Arrays.toString(pair);
            if (set.contains(k) && !seen.contains(s)) {
                count++;
                seen.add(s);
                // uncomment this print statement to print the distinct pairs
                // System.out.println(s);
            } else {
                set.add(arr[i]);
            }
        }
        return count;
    }

    // test suite and driver method
    public static void main(String[] args) {
        System.out.println(count(10, 1, 2, 3, 6, 7, 8, 9, 1) == 3);
        System.out.println(count(47, 6, 1, 3, 46, 1, 3, 9) == 1);
        System.out.println(count(9, 3, 2, 1, 45, 27, 6, 78, 9, 0) == 2);
        System.out.println(count(9, 3, 3, 2, 1, 45, 27, 6, 78, 9, 0) == 2);
        System.out.println(count(6, 1, 5, 7, -1) == 2);
        System.out.println(count(6, 1, 5, 7, -1, 5) == 2);
        System.out.println(count(2, 1, 1, 1, 1) == 1);
        System.out.println(count(5, 1, 2, 2, 2, 3, 4, 4, 4) == 2);
        System.out.println(count(8, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4) == 1);
        System.out.println(count(7, 1, 5, 66, 2, 3, 4, 7, 0, 2, 5) == 3);
        System.out.println(count(5) == 0);            
        System.out.println(count(5, 1) == 0);
        System.out.println(count(7, 3, 4) == 1);
    }
}

Another approach can be to follow the classic solution of Two Sum Problem and add the pairs in a set as you find them, all this in the same pass. This set will be of a custom wrapper class with arr[i] and (target - arr[i]) as it's members and you'll need to override hashcode() and equals() methods in such a way that (a,b) is the same as (b,a). At the end simply return the size of the set. This approach will have the same time and space complexity in Big-O terms as the first approach.

另一种方法可以是遵循二和问题的经典解决方案，并在您找到它们时将它们添加到集合中，所有这些都在同一次传递中。这个集合将是一个自定义包装类，带有 arr[i] 和 (target - arr[i]) 作为它的成员，你需要以这样的方式覆盖 hashcode() 和 equals() 方法 (a,b ) 与 (b,a) 相同。最后简单地返回集合的大小。这种方法在 Big-O 方面将具有与第一种方法相同的时间和空间复杂度。

int count(int target, int... nums) {
    Set<Pair> uniPairs = new HashSet<>();
    Set<Integer> seen = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        int diff = target - nums[i];
        if (seen.contains(diff)) {
            Pair pair = new Pair(nums[i], diff);
            uniPairs.add(pair);
        }
        seen.add(nums[i]);
    }
    return uniPairs.size();
}

class Pair {
    int a;
    int b;
    public Pair (int a, int b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public boolean equals(Object obj) {
        Pair pair2 = (Pair) obj;
        return ((a == pair2.a) && (b == pair2.b)) || ((b == pair2.a) && (a == pair2.b));
    }

    @Override
    public int hashCode() {
        return Objects.hash(a, b) + Objects.hash(b, a);
    }
}

回答by Robert

You can slove by using below code:

您可以使用以下代码进行 slove：

def countPairs(arr, k):
    possible_maps = []

    for num in arr:
        pair_matches = list(filter(lambda n: n + num == k, arr))

        if len(pair_matches) > 0:
            possible_maps += list(map(lambda nm: (num, nm), pair_matches))

    return len(set(map(lambda pair: ','.join(str(n) for n in sorted(pair)), possible_maps)))

Hope this may help you.

希望这可以帮助你。

回答by Ganesh Jadhav

The code takes an array and returns all possible pairs that have sum as specified. As the question asks to print number of pairsand not the pairs, the length of array divided by 2 would give the desired answer.

该代码采用一个数组并返回具有指定总和的所有可能对。由于问题要求打印对数而不是对数，数组的长度除以 2 将给出所需的答案。

int notInArray(float a[],float m,int n)
{
   int i,j,k;
   for(i=0;i<n;i++)
   {
       if(a[i] == m)
           return 0;
   }
   return 1;


}
int main() {

   int i,j,k;
   int n;
   scanf("%d",&n);   //Input the number of elements in array.

   float arr[n];

   for(i=0;i<n;i++)
       scanf("%f",&arr[i]);   //input the array elements


   float copyArr = arr[0];

   float m;

   if (n == 0)
       return 0;

   scanf("%f",&m);   //input the sum

   float resArr[n];
   int b;
   int a=b=0;

   for(i=0;i<n;i++)
   {
       for(j=i+1;j<n;j++)
       {
           if(arr[i]+arr[j]==m && notInArray(resArr,arr[i],n))
           {
               resArr[a++] = arr[i];
               resArr[a++] = arr[j];

               //printf("%.0f %.0f\n",arr[i],arr[j]);
           }
       }
   }

   printf("All possible pairs: \n");
   for(i = 0;i<a;i+=2)
       printf("%.0f %.0f\n",resArr[i],resArr[i+1]);

   int len = (int)( sizeof(resArr) / sizeof(resArr[0]) )
   printf("Number of such pairs: %d",len);
   return 0;
}

回答by nvntkmr

    public void distinctPairs(int[] arr, int k){
    int length = arr.length;
    int count = 0;
    Map<Integer,Integer> pairs = new HashMap<Integer,Integer>();
    for(int i=0;i<length;i++){
        for(int j=i+1;j<length;j++){
            if(arr[i]+arr[j] == k ){
                if(!(pairs.containsKey(arr[j])&&pairs.containsValue(arr[i]))) 
                pairs.put(arr[i], arr[j]);
            }
        }
    }
    count = pairs.size();
    System.out.println("Pairs are "+pairs+"  count  = "+count);
}

This works for me. Steps I followed.

这对我有用。我遵循的步骤。

1. Check if sum of a pair is equal to required(k).
2. Check if the pair doesn't already exist in the map.

1. 检查一对总和是否等于 required(k)。
2. 检查该对是否已存在于地图中。

回答by Kishan Maurya

We can use the hashmap to store all values of the array. Then iterate over the array and check if the map contains (K - a[i] ). If the map contains then increment count and remove both keys from the map.

我们可以使用 hashmap 来存储数组的所有值。然后遍历数组并检查地图是否包含 (K - a[i] )。如果地图包含，则增加计数并从地图中删除两个键。

private int getDistinctPair(int k,int[] input){
        HashMap<Integer,Integer> map = new HashMap<>();
        int pairs = 0;
        for (int i = 0; i < input.length-1; i++) {
            map.put(input[i], input[i]);
        }
        for (int i = 0; i <input.length-1 ; i++) {
            int diff = k - input[i];
            if(map.containsKey(diff)){
                pairs++;
                map.remove(diff);
                map.remove(input[i]);
            }
        }
        return  pairs;
    }

回答by Rubasace

public static int sumPairs(Integer[] input, int sum){
    List<Integer> complementaries = new ArrayList<>(input.length);
    int pairs = 0;
    for(Integer number : input){
        if(complementaries.contains(number)){
            complementaries.remove(number);
            pairs++;
        }
        else{
            complementaries.add(sum-number);
        }
    }
    return pairs;
}

Now it should work perfectly.

现在它应该可以完美运行。

The complementaries array is used just for keeping track of the numbers needed for making the sum. If it contains the number it means that we iterated over its complementary before, so we can just add one pair and remove the number from the list of complementaries. Oherwise we add the complementary of the current number to the list without incresing the pairs counter.

互补数组仅用于跟踪求和所需的数字。如果它包含数字，则意味着我们之前迭代了它的补码，因此我们可以添加一对并从补码列表中删除该数字。否则，我们将当前数字的互补添加到列表中，而不增加对计数器。

回答by Md. Ashik Ali Khan

The Simplest Solution of your problem of finding distinct pair:

找到不同对的问题的最简单解决方案：

public static int SumPairs(int[] input, int k) {

    Map<Integer, Integer> pairs = new HashMap<Integer, Integer>();
    int tmp = 0;
    for (int data : input) {
        if (pairs.containsKey(k - data) && pairs.get(k - data) == 0) {
            tmp++;
            pairs.put((k - data), pairs.get(k - data) + 1);
        } else if (!pairs.containsKey(data)) {
            pairs.put(data, 0);
        }
    }

    return tmp;
}

It has been tested for 1 2 2 2 3 4 4 4 and sum = 5. Also for 4 4 4 4 4 4 4 4 4 4 4 4 4 4 and sum = 8. If any confusion feel free to ask me. Cheers.

它已被测试为1 2 2 2 3 4 4 4 和 sum = 5。同样对于4 4 4 4 4 4 4 4 4 4 4 4 4 4 和 sum = 8。如果有任何困惑，请随时问我。干杯。

回答by Duraivel

import java.util.HashSet;
public class DistinctPairs {     
   static int numberOfPairs(int[] arr,int k)
   {
       HashSet<String> s=new HashSet<String>();
       int n=arr.length;
       int sum=0;
       for(int i=0;i<n;i++)
       {
           for(int j=0;j<n;j++)
           {
               sum=arr[i]+arr[j];
               if(i==j)
               {
                   continue;
               }
               else
               {
                  if(sum==k)
                  {
                      String l=String.valueOf("("+arr[i]+","+arr[j]+")");
                      StringBuilder sb=new StringBuilder(l);
                      String rl=sb.reverse().toString();
                      if(s.add(l)==false)
                      {

                      }

                  }
               }

           }
       }
        System.out.println(s.toString());

       return s.size()/2;
   }
    public static void main(String args[])
    {
        int b[]={1,5,66,2,3,4,7,0,2,5};
     int size=numberOfPairs(b,5);  
     System.out.println(size);
    }
}