w508主题,儿行千里伴奏,庶出庶出19楼
这是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 }
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论