a 5ms for two number,,,hash type


  • 0
    R

    /**

    • Note: The returned array must be malloced, assume caller calls free().
      */

    typedef struct mmp *pMap;

    typedef struct mmp{
    int index;
    int value;
    pMap pNext;
    }map_obj;
    #define HASH_CAL 500
    int* twoSum(int nums[], int numsSize, int target) {
    int i,j,k;
    int * arr = (int*)malloc(8);

    map_obj hash[HASH_CAL];
    
    for(i=0;i<HASH_CAL;i++)
    {
        hash[i].index = -1;
        hash[i].value = 1;//
        hash[i].pNext = NULL;
    }
    
    for(i=0;i<numsSize;i++)
    {
        int bias = abs(nums[i])%HASH_CAL;
    	
        if(hash[bias].index == -1)
        {
            hash[bias].value = nums[i];
            hash[bias].index = i;
        }
        else 
        {
            map_obj *new1 = (map_obj*)malloc(sizeof(map_obj)*1);
    
            new1->index = i;
            new1->value = nums[i];
            new1->pNext = hash[bias].pNext;
            hash[bias].pNext = new1;
        }
    }
    
    for(i=0;i<numsSize;i++)
    {
        int bias = (abs(target-nums[i]))%HASH_CAL;
    	map_obj tmp ;
    	
        if(hash[bias].index == -1)continue;
        else
        {
    		tmp.index = hash[bias].index;
    		tmp.pNext = hash[bias].pNext;
    		tmp.value = hash[bias].value;
    		while(1)
    		{
                if((tmp.index != i) &&((nums[i]+nums[tmp.index]) == target))
                {
                    arr[0] = i;
                    arr[1] = tmp.index;
    
                    return arr;
                }
                else
                {
                    if(tmp.pNext!=NULL)
                    {
                       tmp.index = tmp.pNext->index;
                       tmp.value = tmp.pNext->value;
                       tmp.pNext = tmp.pNext->pNext;
                        
                    }
    				else
    				{
    					break;
    				}
                }
            }
        }
    }
    arr[0] = -1;
    arr[1] = -1;
    return arr;
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.