15.三数之和

思路

直接遍历的话可能要O(n**3)时间复杂度太大了,我们需要应用哈希表尽量减小时间复杂度,但基本还是遍历,因此时间复杂度不会低

• 我们先排序来减少需要的时间,下一步就知道为什么了,c语言没有.sort,我又不想写一个快排,这里直接用qsort了,需要前置函数

  int compare(const void* a,const void* b){
  	return (*(int*)a-*(int*)b);//升序排序
  }
  qsort(nums,sizeof(nums)/sizeof(nums[0]),sizeof(int),compare);

• 来两个指针,可以想到需要left遍历整个数组,当数组内容相同时直接跳过,因为我们已经排序好了,因此我们只需要:

  if (nums[i]==nums[i-1]){
  continue;
  }
  就行了

• 接下来的思路就是很正常的遍历了,让left指向开头,right向右走,把-(nums[left]+nums[right])放入哈希表,存在nums[right]==哈希表里的值就输出

  int compare(const void* a, const void* b) {
      return *(int*)a - *(int*)b;
  }
  
  struct hashTable {
      int key;
      int val;
      UT_hash_handle hh;
  };
  
  struct hashTable* hashtable = NULL;
  
  struct hashTable* find(int ikey) {
      struct hashTable* tmp;
      HASH_FIND_INT(hashtable, &ikey, tmp);
      return tmp;
  }
  
  void insert(int ikey, int ival) {
      struct hashTable* it = find(ikey);
      if (it == NULL) {
          struct hashTable* tmp = malloc(sizeof(struct hashTable));
          tmp->key = ikey;
          tmp->val = ival;
          HASH_ADD_INT(hashtable, key, tmp);
      } else {
          it->val = ival;
      }
  }
  
  void clearHashTable() {
      struct hashTable *current, *tmp;
      HASH_ITER(hh, hashtable, current, tmp) {
          HASH_DEL(hashtable, current);
          free(current);
      }
  }
  
  int** threeSum(int* nums, int n, int* returnSize, int** returnColumnSizes) {
      qsort(nums, n, sizeof(int), compare);
      int capacity = n * n;  // 设置一个合理的初始大小
      int** ans = malloc(capacity * sizeof(int*));
      *returnColumnSizes = malloc(capacity * sizeof(int));
      *returnSize = 0;
  
      for (int left = 0; left < n - 2; left++) {
          if (left > 0 && nums[left] == nums[left - 1]) {
              continue;  // 跳过重复元素
          }
          if(nums[left]+nums[left+1]+nums[left+2]>0){
              continue;
          }
          if(nums[left]+nums[n-1]+nums[n-2]<0){
              continue;
          }
          
          clearHashTable();
          for (int right = left + 1; right < n; right++) {
              int target = -(nums[left] + nums[right]);
              struct hashTable* now = find(target);
              if (now != NULL) {
                  int* ret = malloc(3 * sizeof(int));
                  ret[0] = nums[left];
                  ret[1] = target;
                  ret[2] = nums[right];
                  
                  ans[*returnSize] = ret;
                  (*returnColumnSizes)[*returnSize] = 3;
                  (*returnSize)++;
                  
                  // 跳过重复元素
                  while (right + 1 < n && nums[right] == nums[right + 1]) right++;
              }
              insert(nums[right], 1);
          }
      }
      
      return ans;
  }

  但是还是超时!,或许python和java可以实现,我们将哈希表换成双向指针来实现

  

双向指针

int compare(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int** threeSum(int* nums, int n, int* returnSize, int** returnColumnSizes) {
    qsort(nums, n, sizeof(int), compare);
    int** ans = malloc(n*n * sizeof(int*));
    *returnColumnSizes = malloc(n*n * sizeof(int));
    int m=0;

    for (int left = 0; left < n - 2; left++) {
        if (left > 0 && nums[left] == nums[left - 1]) {
            continue;  // 跳过重复元素
        }
        if(nums[left]+nums[left+1]+nums[left+2]>0){
            break;
        }
        if(nums[left]+nums[n-1]+nums[n-2]<0){
            continue;
        }
        
        int mid=left+1;
        int right=n-1;
        
        while(mid<right){
            int sum=nums[left]+nums[right]+nums[mid];
            if(sum>0){
                right--;
            }
            else if(sum<0){
                mid++;
            }else{
                int* tmp=malloc(3*sizeof(int));
                tmp[0]=nums[left];
                tmp[1]=nums[mid];
                tmp[2]=nums[right];

                ans[m]=tmp;
                (*returnColumnSizes)[m++]=3;

            ++mid;--right;
            while(mid<right&&nums[mid]==nums[mid-1])mid++;
            while(mid<right&&nums[right]==nums[right+1])right--;
            }
        }
    }

    *returnSize=m;
    return ans;
}