首页 > > 程序设计 > C/C++ >

Two Sum

2018-06-18 03:51:47来源：未知阅读 ()

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 }