Share Accepted O(n) 4ms C solution


  • 0
    W

    Welcome to share your suggestions for further improvement! :)

    int *twoSum(int numbers[], int n, int target) {
        static int res_c[2] = {0};
    //    int *res_c = (int *)malloc(2*sizeof(int));
        if(n < 2)
            return res_c;
        int set[100000] = {0};
        for(int i=0; i < n; ++i) {
            if(numbers[i] < -50000 || numbers[i] >= 50000)
                return res_c;  //in fact: there should return an error
            set[numbers[i] + 50000] = i + 1;  //plus 1 to change 0 based index to 1 based index
        }
        for(int i=0; i<n; ++i) {
            if(set[target - numbers[i] + 50000]) {
    //            cout << "i=" << i << ", numbers[i]=" << numbers[i] << ", set[numbers[i]]=" << set[numbers[i]] << endl;
                res_c[0] = i + 1;  //plus 1 to change 0 based index to 1 based index
                res_c[1] = set[target - numbers[i] + 50000];
                if(res_c[0] != res_c[1]) 
                    break;
            }
        }
       if(res_c[0] == res_c[1])
            res_c[0] = res_c[1] = -1;
        return res_c;
    }

  • 0
    D
    #define SIZE 256
    
    struct hash_table
    {
      int key;
      int value;
    };
    
    struct hash_map
    {
      struct hash_table **ht;
    };
    
    struct hash_table* hash_table_int(int key, int value)
    {
      struct hash_table *h = (struct hash_table*)malloc(sizeof(struct hash_table*));
      h->key =key;
      h->value = value;
      return h;
    }
    
    int get_value(struct hash_map *hm, int key)
    {
     int hash = (key % SIZE);
     if (hash<0) {
       return -1;
     }
     while (hm->ht[hash] != NULL && hm->ht[hash]->key != key) {
       hash = (hash+1)%SIZE;
     }
     if (hm->ht[hash] == NULL) {
       return -1;
     } else {
       return hm->ht[hash]->value;
     }
    }
    
    void put_value(struct hash_map *hm, int key, int value)
    {
      int hash = (key % SIZE);
      if (hash<0) {
       return;
      }
      while (hm->ht[hash] != NULL && hm->ht[hash]->key != key) {
        hash = (hash+1)%SIZE;
      }
      if (hm->ht[hash] != NULL) {
        printf("\nDUP\n");
        free(hm->ht[hash]);
      }
      hm->ht[hash] = hash_table_int(key, value);
    }
    
    void free_hm(struct hash_map *hm)
    {
      for (int i=0; i< SIZE; i++) {
        if (hm->ht[i] != NULL) {
          free(hm->ht[i]);
        }
      }
      free(hm);
    }
    
    struct hash_map * new_hm()
    {
      struct hash_map *hm = (struct hash_map*)malloc(sizeof(struct hash_map*));
      hm->ht = (struct hash_table**)malloc(sizeof(struct hash_table*)*SIZE);
      for (int i=0; i<SIZE; i++) {
        hm->ht[i] = NULL;
      }
      return hm;
    }
    
    int two_sum(int *arr, int len, int target, int *p)
    {
      int i;
      p = (int*)malloc(sizeof(int)*2);
    
      struct hash_map *hm = new_hm();
      for (i=0; i<len; i++) {
        put_value(hm, arr[i], i);
      }
      for (int j=0; j<len; j++) {
        int val = get_value(hm, target-arr[j]);
        if (val != -1) {
          p[0] = j+1;
          p[1] = val+1;
          printf("\n%d %d\n", j, val);
          printf("\n%d %d\n", arr[j], target-arr[j]);
          free_hm(hm);
          return 1;
        }
      }
      free_hm(hm);
      return 0;
    }

  • 0
    W

    Do you think your solution is better than mine?


  • 0
    D

    No. I just pasted my solution using hash table


  • 0
    G

    where did you test the program ? Is it can be judged by leetcode ?


  • 0
    G

    What if there is same number in the array ? For example, input array is [0, 1, 2, 0] and target is 0 ?


  • 0
    D

    On leetcode it is giving me "Output Limit Exceeded" error. If I use gcc v4.4.7 compiler it runs and gives valid output for the sample input of the problem "numbers={2, 7, 11, 15}, target=9" and other random samples inputs which I tried.

    It would be great if you can help me overcome the error message! Thanks!

    PS: My motive to paste the solution was to help googler browse a hash table based solution.


Log in to reply
 

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