两数之和
思路
注：本题只采用暴力解法，时间复杂度为O(n2)，如果采用哈希表，可以将时间复杂度降到O(n)，但由于笔者还未对哈希表展开学习，故不做讨论
- 我们直接用两层for循环来解决问题
- 第一层for循环用来遍历整个数组，第二层for循环用来判断遍历的两个数的和是否等于target
for(int i = 0; i < numsSize - 1; i++) { for(int j = i + 1; j < numsSize; j++) { if(nums[i] + nums[j] == target) { ……………………; } } }
实现代码
int* twoSum(int* nums, int numsSize, int target, int* returnSize){ //确定返回数组的大小 *returnSize = 2; //申请的返回数组 int *res = (int *)malloc(sizeof(int) * 2); //寻找满足条件的两个数 for(int i = 0; i < numsSize - 1; i++) { for(int j = i + 1; j < numsSize; j++) { if(nums[i] + nums[j] == target) { res[0] = i; res[1] = j; } } } //返回这两个数的下标 return res; }
拓展
- 这道题要求返回的是满足条件的两个数的下标，但如果将题目要求改为返回这两个数的值呢？
思路
实现代码
void Sort(int *nums, int numsSize) { for(int i = 0; i < numsSize - 1; i++) { for(int j = i + 1; j < numsSize; j++) { if(nums[i] > nums[j]) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } } } int* twoSum(int* nums, int numsSize, int target, int* returnSize){ int *res = (int *)malloc(sizeof(int) * 2); *returnSize = 2; //排序 Sort(nums,numsSize); //从数组的头和尾对数组进行遍历 int i = 0, j = numsSize - 1; //找到符合条件的两个数 while(i < j) { if(nums[i] + nums[j] > target) j--; else if(nums[i] + nums[j] < target) i++; else { res[0] = nums[i]; res[1] = nums[j]; break; } } //返回数组 return res; }
