leetcode的第一题，很简单。
题目如下
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].
时间复杂度为O(n)的一种解法为：
1 int* twoSum(int* nums, int numsSize, int target) 2 { 3 int index[100001] = {0}, *index_plus_one = index + 50000;//索引从index数组的第50000个元素开始，避免出现负数索引报错； 4 for (int i = 0; i < numsSize; i++) 5 { 6 int rest = target - nums[i]; 7 if (index_plus_one[rest]) 8 { 9 //如果rest这个索引已经计算过了，那么就可以得出答案 10 int *ans = malloc(sizeof(int) * 2); 11 ans[0] = i; 12 ans[1] = index_plus_one[rest] - 1; 13 return ans; 14 } 15 else 16 index_plus_one[nums[i]] = i + 1;//如果rest这个索引没有计算过，那么就将 index_plus_one[nums[i]] 标记为大于0； 17 } 18 return NULL; 19 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
