寻找和为定值的两个数

题目：

输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。

要求时间复杂度是O(N)。如果有多对数字的和等于输入的数字，输出任意一对即可。

例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

 

思路：采用hash方式求解

#include <stdio.h>
#include <stdlib.h>
const int size = 25;
typedef struct node
{
    int data;
    struct node* next;
}*BiNode;
BiNode head[size];
/*获取hash的index*/
int getHashKey(int data)
{
    return data%size;
}
/*将data插入到hash表中*/
int insertHash(int data)
{
    int index = getHashKey(data);
    node* p = head[index];
    node* newNode = NULL;
    
    while (p != NULL)
    {
        if (p->data == data)
        {
            return 0;
        }
        p = p->next;
    }
    
    newNode = (node *)malloc(sizeof(node));
    newNode->data = data;
    newNode->next = head[index];
    head[index] = newNode;
    return 0;
}
/*找到data是否在hash表中*/
bool findHashData(int data)
{
    int index = getHashKey(data);
    node* p = head[index];
    while (p != NULL)
    {
        if (p->data == data)
        {
            return true;
        }
        p = p->next;
    }
    
    return false;
}
/*找到所有和等于sum的数对*/
int findSumData(int *a, int len, int sum)
{
    int i;
    for (i=0; i<len; i++)
    {
         insertHash(a[i]);
    }
    
    for (i=0; i<len/2; i++)
    {
         if (findHashData(sum-a[i]))
         {
            printf("%d + %d = %d
", a[i], sum-a[i], sum);
         }
    }
    return  0;
}
int main()
{
    int a[] = {1, 2, 4, 7, 11, 15};
    
    findSumData(a, 6, 11);
}