# 题目：

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

# 思路：

1：这道题可以参考《【程序员编程艺术】第五章：寻找满足和为定值的两个或多个数》但该题目中建立hash表时用bitmap来实现，是链接中所没有的。

2：关于bitmap可以参考：bitmap应用及实现

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//快速排序
int Position(int arr[],int lo,int hi)
{
int key = arr[hi];
int i = lo - 1;
int temp;

for(int j = lo;j < hi;j++){
if(arr[j] < key){
++i;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
++i;
temp = arr[i];
arr[i] = arr[hi];
arr[hi] = temp;

return i;
}

void QuickSort(int arr[],int lo,int hi)
{
int mid;
if(lo < hi){
mid = Position(arr,lo,hi);
QuickSort(arr,lo,mid - 1);
QuickSort(arr,mid + 1,hi);
}
}

//bitmap实现
unsigned char *g_bitmap = NULL;
int g_size = 0;
int g_base = 0;

int bitmap_init(int size,int start)
{
g_bitmap = (unsigned char *)malloc((size/8 + 1) * sizeof(char));
if(g_bitmap == NULL)
exit(1);
g_base = start;
g_size = size/8 + 1;

memset(g_bitmap,0,g_size);
return 1;
}

int bitmap_set(int index)
{
int quo = (index - g_base)/8;
int remainder = (index - g_base)%8;
unsigned char x = 1 << remainder;   //x必须设为char字符，接下来要与一个字节的数据相与

if(quo >= g_size)
return 0;
g_bitmap[quo] |= x;

return 1;
}

int bitmap_get(int i)
{
int quo = i/8;
int remainder = i%8;
unsigned char x = 1 << remainder;
unsigned char res;
if(quo >= g_size)
return 0;
res = g_bitmap[quo] & x;

return res > 0 ? 1 : 0;
}

int bitmap_data(int i)
{
return i+g_base;
}

void bitmap_free(void)
{
free(g_bitmap);
}

//找到合适的解
int FindTwoSum(int arr[],int key,int n,int *x,int *y)
{
int i,j;

for(i = 0,j = n-1;i < j;){
if(arr[i]+arr[j] == key){
*x = i;
*y = j;
return 1;
}else if(arr[i] + arr[j] > key)
--j;
else
++i;
}

return 0;
}

void PrintArr(int arr[],int n)
{
for(int i = 0;i < n;++i)
printf("%d ",arr[i]);
printf("\n");
}

int main(void)
{
int n,index1,index2;
int arr[] = {7,2,15,11};
n = sizeof(arr)/sizeof(int);
#if 0
PrintArr(arr,n);
QuickSort(arr,0,n-1);
PrintArr(arr,n);
FindTwoSum(arr,9,n,&index1,&index2);
printf("index1 = %d,index2 = %d",index1,index2);
#endif // 0

bitmap_init(15,0);
for(int i = 0;i < n;i++){
bitmap_set(arr[i]);
}
int j = 0;
for(int i = 0;i <= 15 && j < n;i++){
if(bitmap_get(i))
arr[j++] = bitmap_data(i);
}
PrintArr(arr,n);
FindTwoSum(arr,9,n,&index1,&index2);
printf("index1 = %d,index2 = %d",index1,index2);
return 0;
}``````