leetcode系列1-两数之和

【题目概要】

1. Two Sum 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. Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

【思路解析】

每一个target均有对应的一个解，因此不需要考虑多种不同解的情况

不允许存在一个数使用两次的情况，需要剔除这种解

两层遍历数组的方式，外层遍历至numsSize-2，内层从index+1开始到numsSize-1，查找符合条件值，返回即可，时间复杂度O(n²)

【代码示例1】

int* twoSum(int* nums, int numsSize, int target, int* returnSize){ if(numsSize <= 0) return NULL; int *rearry = (int*)malloc(sizeof(int)*2); *returnSize = 2; for(int index=0; index<numsSize-1; index++) { int nextindex = numsSize-1; int key = target-nums[index]; while(nextindex>index && nums[nextindex] != key) { nextindex--; } if(nums[nextindex] == key && nextindex != index) { rearry[0] = index; rearry[1] = nextindex; break; } } return rearry; }

【代码示例2】

int* twoSum(int* nums, int numsSize, int target, int* returnSize){ int *re = (int*)malloc(sizeof(int)*2); for(int i=0; i<numsSize-1; i++) { for(int j=i+1; j<numsSize; j++) { if(nums[i] == target-nums[j]) { re[0] = i; re[1] = j; *returnSize = 2; break; } } } return re; }

提交结果显示代码示例1要优于示例2