毕业一年后第一次回顾C语言

已经差不多两年没有摸代码了
写了力扣第一题，两数求和，已经很生疏了

本次回顾了三个知识点

• 指针名作为变量代表这段地址（即使没有分配）的第0个index

• 使用*号可以对该地址进行解引用，解引用可以进行如下赋值操作：

  int* p = (int*)malloc(sizeof(int) * n);
  *p = 1;
  *p + 2 = 2;
  *p + 3 = 100;

  没解引用可以

  p[0] = 1;
  p[1] = 2;
  p[3] = 100;

  两种不同赋值方法而已

• 快忘记的一点是for循环的三个条件，第一个是赋值，第二个是判断（符合执行、不符合跳出）第三个是执行完本次之后进行的操作

题目编号为1，使用暴力解法，时间复杂度为O(n2)

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int frontIndex = 0;
    int rearIndex = numsSize - 1;
    int* result = (int*)malloc(2 * sizeof(int));
    *returnSize = 0;
    for(int i = frontIndex;i < rearIndex;i++){
        if(i != numsSize){   //防止j越界
            for(int j = i + 1;j < numsSize;j++){
                if(nums[i] + nums[j] == target){    //暴力找到解
                    result[0] = i;
                    result[1] = j;
                    *returnSize = 2;
                    return result;
                }
            }
        }
    }
    free(result);   //未找到解  释放内存
    return 0;
}

如何突破O(n2)的复杂度呢？

---

• 分类： 算法回顾
• 标签： 无标签