如果找对元素与既定总和大整数数组存在 [英] Find if pair of elements with given sum exists in large integer array

问题描述

我有10万台，如何写在C＃中，如果数组有一对总结75返回true函数的整数数组。

我的代码是：

  INT总和= 75，最大=千万; 
 INT []数组=新INT [MAX]; 
布尔checkFlag = FALSE; 
随机RND =新的随机（）; 
秒表SW = Stopwatch.StartNew（）; 
 
的for（int i = 0; I<最大;我++）
 {
数组[我] = rnd.Next（0，最大值* 20）; 
} 
的Array.Sort（数组）; 
如果（阵列[0] +阵列[1] =总和）
 {
 Console.WriteLine（{0} + {1} = {2}，数组[0 ]数组[1]，数组[0] +阵列[1]）; 
 checkFlag = TRUE; 
} 
 Console.WriteLine（总和高达75是：+ checkFlag）; 
  

解决方案

这会如果数组进行排序工作。

 公共BOOL ContainsPair（INT []数组），
 {
 INT I = 0; 
 INT J = array.Length  -  1; 
，而（I< j）条
 {
如果（阵列[I] +阵列[J] == 75）
返回真; 
，否则如果（阵列[I] +阵列[J]< 75）
 I ++; 
，否则如果（阵列[I] +阵列[J]> 75）
 j--; 
} 
返回FALSE; 
} 
  

您使用两个指针和对数组的中间行走。指针 I 开始在数组的开头，而Ĵ开始于结束。如果您发现总结75两个数字，就返回true。如果总和小于75，那么你移动指针 I 一个向中间步骤，并再次检查。如果总数超过75个，移动指针Ĵ朝中间的一个步骤，并再次检查。

如果这两个指针相遇，那么你就返回false，因为没有一双发现。

这是O（n），不包括排序数组。

I'm having a integer array of 10 Million elements, how to write a function in C# which returns True if the array has a pair which sums up to 75.

My code is:

        int sum = 75, max = 10000000;
        int[] array = new int[max];
        bool checkFlag = false;
        Random rnd = new Random();
        Stopwatch sw = Stopwatch.StartNew();

        for (int i = 0; i < max; i++)
        {
            array[i] = rnd.Next(0, max * 20);
        }
        Array.Sort(array);
        if (array[0] + array[1] <= sum)
        {
            Console.WriteLine("{0} + {1} = {2}", array[0], array[1], array[0] + array[1]);
            checkFlag = true; 
        }
        Console.WriteLine("Sum upto 75 is: " + checkFlag);

解决方案

This will work if the array is sorted.

public bool ContainsPair(int[] array) 
{
    int i = 0;
    int j = array.Length - 1;
    while(i < j)
    {
        if (array[i] + array[j] == 75) 
            return true;
        else if (array[i] + array[j] <  75) 
            i++;
        else if (array[i] + array[j] >  75) 
            j--;
    }
    return false;
}

You use two pointers and walk towards the middle of the array. Pointer i starts at the beginning of the array, while j starts at the end. If you find two numbers that sum up to 75, you return true. If the sum is less than 75, then you move pointer i one step towards the middle and check again. If the sum is more than 75, you move pointer j one step towards the middle and check again.

If the two pointers meet, then you return false, because no pair was found.

This is O(n), not including sorting the array.

这篇关于如果找对元素与既定总和大整数数组存在的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！