leetcode 001--Two Sum

problem:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Difficulty:Easy

hint1:

• 非有序表，采用折半查找出错
• 返回指针值的函数返回数组会出错

采用暴力破解法，穷举所有的数，时间复杂度为O(n^2)

code:

#include<stdio.h> 
#include<malloc.h>
int* twoSum(int*nums,int numsSize,int target){
    int *arr = (int*)malloc(2*sizeof(int)),i,j;
    for(i =0;i<numsSize;i++){
        for(j =i+1;j<numsSize;j++){
            if(nums[i]+nums[j]==target){
                arr[0]=i;
                arr[1]=j;
            }
        }
    }
    return arr;
}
int main(){
    int arr[3] = {2,3,4};
    int target = 6;
    int a[2];
    int *index = a;
    index = twoSum(arr,3,target);
    printf("%d....%d",index[0],index[1]);
}

hint2:

采用用hash存储，空间换时间，最终时间复杂度为O(n)

int* twoSum(int*nums,int numsSize,int target){
    int min,max,len,i;
    int *arr = (int*)malloc(2*sizeof(int));
    min = nums[0];
    for(i = 1;i < numsSize;i++){
        if(min > nums[i]){
            min = nums[i];        //获取输入数组中最大的数值用以确定hash表的头部位置
        }
    }
    max = target - min;     //计算出可能得到的符合条件的最大数  
    len = max - min + 1;      //len代表可能取到的最大的数 
    int *h = (int*)malloc(len*sizeof(int));
    
    for(i = 0;i<len;i++){
        h[i]=-1;                //初始化hash表
    }
    for(i = 0;i<numsSize;i++) {
        if(nums[i]-min<len){
            if(h[target-nums[i]-min] != -1){
                arr[0] = h[target-nums[i]-min];
                arr[1] = i;
                return arr;
            }
            h[nums[i]-min] = i;     //若未找到则存储进hash表中
        }
    }
    free(h);
    return arr;
}