0

I am solving a leetcode 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."

I was able to solve the problem if array elements are positive. I created a hashtable which works well for positive numbers. How can I make it to work for non-positive numbers. 

#include "stdio.h"
#include "stdlib.h"
#include "assert.h"


/**
 * Note: The returned array must be malloced, assume caller calls free(). [2,7,11,15]
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){

       //create a hashmap
       int *hashmap = (int*)malloc(100000*sizeof(int));
       int *retarray = NULL;

      //memset all values to -1;
      memset(hashmap,-1,(100000*sizeof(int)));

      int i = 0;
      int complement;

      for(i=0;i<numsSize;i++){
            complement = abs(target-nums[i]);
            if(hashmap[complement]!= -1){
                  *returnSize = 2;
                  retarray = (int*)malloc(*returnSize*sizeof(int));
                  retarray[0] = hashmap[complement];
                  retarray[1] = i;
                  return retarray;
            }
            hashmap[nums[i]] = i;

      }

     *returnSize = 0;
     return retarray;

}

int main(){
    int i = 0;
   // int arr[4] = {2,7,11,15};
    int arr[4] = {-3,3,11,15}; //fails for this.
    int *ret_arr;
    int returnSize;
    ret_arr = twoSum(arr,4,9,&returnSize);
    assert(returnSize==2);
    printf("ret array %d %d \n",ret_arr[0],ret_arr[1]);

}
user968000
  • 1,765
  • 3
  • 22
  • 31
  • Don't cast the result of `malloc()`: https://stackoverflow.com/q/605845 – alx - recommends codidact Jun 13 '19 at 23:55
  • You can use negative indices for accessing arrays too. You just need to create a pointer that points to somewhere in the middle of the `hashmap`, and then you can deference it with a negative index: `int *foo; foo = hashmap + 50000; ... if (foo[-7] != -1) ...` – alx - recommends codidact Jun 14 '19 at 00:00
  • Never use magic numbers. Why `100000`? You should use a macro for that: `#define VALUE_MAX (100000)`. If you use negative numbers, it could be `#define VALUE_MAX (50000)` `#define VALUE_MIN (-50000)` #define HASHMAP_SIZE (VALUE_MAX - VALUE_MIN + 1), and the array size should be `sizeof(*hashmap) * HASHMAP_SIZE)` – alx - recommends codidact Jun 14 '19 at 00:04

0 Answers0