4ms O(n) accepted C solution


  • 5
    X

    /**

    • Note: The returned array must be malloced, assume caller calls free().
      /
      int
      twoSum(int* nums, int numsSize, int target) {

      int i,j;
      int indices = malloc( 2sizeof(int) );
      int max,min;

      max = nums[0];
      min = nums[0];

      for( i=1; i<numsSize; i++ )
      {
      if( nums[i] > max )
      max = nums[i];
      if( nums[i] < min )
      min = nums[i];
      }

      int* repeat_tag = malloc( (max-min+1)*sizeof(int) );
      memset( repeat_tag, 0, (max-min+1)*sizeof(int) );

      int diff;

      for( i=0; i<numsSize; i++ )
      {
      diff = target-nums[i];

       if( ( diff <= max ) && ( diff >= min ) ) 
           repeat_tag[ diff-min ] = i;
      

      }

      for( i=0; i<numsSize; i++ )
      {
      if( repeat_tag[nums[i]-min] != 0 )
      {
      // exclude the case in which two indices are the same.
      if( i != repeat_tag[nums[i]-min] )
      {
      indices[0] = i;
      indices[1] = repeat_tag[nums[i]-min];
      return indices;
      }
      }
      }

      return NULL;
      }


  • 0
    W

    Excited! what an awsome solution! If the input size is very large and the memory size is enough to be ignored, this is a good solution.

    But why no guys here to give a post and back up?


  • 0
    1

    @xiame excellent!!!


Log in to reply
 

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