找了个leeCode最简单的题做，结果发现要做到O(n)还是好麻烦……
#include <stdio.h> #include <stdlib.h> typedef struct TANode { int pos; struct TANode *next; }TA,*TAP; int* twoSum(int* nums, int numsSize, int target) { int max=nums[0],i,offset,min=nums[0]; for(i=1;i<numsSize;i++) { if(nums[i]>max) max=nums[i]; if(nums[i]<min) min=nums[i]; } if(min<0) min=-min; int *r=(int*)malloc(2*sizeof(int)); TA *ta=(TA *)malloc((max+min+1)*sizeof(TA)); for(i=0;i<(max+min+1);i++) { ta[i].pos=-1; ta[i].next=NULL; } for(i=0;i<numsSize;i++) { if(ta[nums[i]+min].pos==-1) { ta[nums[i]+min].pos=i; } else { TAP t=(TAP)malloc(sizeof(TA)); t->pos=i; t->next=NULL; ta[nums[i]+min].next=t; } } for(i=0;i<numsSize;i++) { int x=nums[i],y; if(target-x+min>=0 && ta[target-x+min].pos != -1) { if(i<ta[target-x+min].pos) { r[0]=i; r[1]=ta[target-x+min].pos; return r; } else if(i>ta[target-x+min].pos) { r[0]=ta[target-x+min].pos; r[1]=i; return r; } else { TAP t=&ta[target-x+min]; if(t->pos==i) { t=t->next; } if(t) { r[0]=i; r[1]=t->pos; return r; } } } } return r; } void printA(int *a,int len) { for(int i=0;i<len;i++) { printf("%d ",a[i]); } } void main() { int nums[3]={3,3,6}; int *r=twoSum(nums,3,6); printA(r,2); getchar(); }