[LeetCode] 1. Two Sum-白红宇

[LeetCode] 1. Two Sum

阅读量：4569 次

发布时间：2019-06-08

本文共 3217 字，大约阅读时间需要 10 分钟。

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]. https://leetcode.com/problems/two-sum/description/ LeetCode刷题做到的第一道题，刚开始就是很普通的暴力搜索思想(两重循环)，代码如下。

1 int *twoSum(int *nums, int numsSize, int target){ 2     static int a[2]; 3     int flag = 0; 4     for (int i = 0; i < numsSize; i++){ 5         for (int j = i + 1; j < numsSize; j++){ 6             if (nums[i] + nums[j] == target){ 7                 a[0] = i; 8                 a[1] = j; 9                 flag = 1; break;10             }11         }12         if (flag == 1) break;13     }14     return a;15 }

View Code

刚开始容易犯个错误，就是没有加static，leetcode上运行的时候报错 “load of null pointer of type 'const int' ”，然后加上static 后可以成功运行，并且提交通过。

然而，不难看出，算法复杂度是O(n^2)，这样是很容易超时的。所以得想办法降低时间复杂度。

经过网上查阅资料，看前人的博客，大部分是使用哈希表，或者类似哈希表思想的方法来降低复杂度。

法一（C语言）：

使用malloc动态建立数组，map[]作为映射表。首先，找出所有数字中最小的一个数min，所以在最后结果中，我们要选的两个数的范围应该是【min, target-min】。

给这个范围内的每个数字建立哈希表。（key, value）。key是数字，value是它对应的下标。用C语言的数组来表述就是，map[i] = j。i 是key, j是value。还要注意每次两个数的大一不等。O(n)

1 int *twoSum(int* nums, int numsSize, int target) { 2     //找到min，max为target-min； 3     int min = 2147483647; 4     for (int i = 0; i < numsSize; i++){
    //找到数组中最小的一个数 5         if (nums[i] < min){ 6             min = nums[i]; 7         } 8     } 9     int max = target - min;10     int len = max - min + 1;11     int *map = (int*)malloc(len*sizeof(int));//建立映射表12     int *ret = (int*)malloc(2*sizeof(int));13     for (int i = 0; i < len; i++){
    //初始化映射表14         map[i] = -1;15     }16 17     for (int i = 0; i < numsSize; i++){18         if (nums[i] - min < len){19             map[nums[i] - min] = i;20         }21     }22     for (int i = 0; i < numsSize; i++){23         if (nums[i] - min < len){
    //筛去所有不符合条件的数字，比如说：target= 9；min = 2；8就不符合。都不用进判断24             if (map[target - nums[i] - min] != -1){ //判断相加是否是target25                 ret[0] = i;26                 ret[1] = map[target - nums[i] - min];//map的value里面存的是满足条件的数在数组中的下标27                 if (i != map[target - nums[i] - min])return ret;28             }29         }30     }31     return NULL;32 }

View Code

法二（C++）：

C++中有map模板。O（n）

1 #include
      
        2 #include
       
         3 #include
         4 //#include
         
           5 #include
          
            6 using namespace std; 7 class Solution { 8 public: 9     vector
           
             twoSum(vector
            
             & nums, int target) {10 map
             
               myMap;11 vector
              
                res;12 vector
               
                ::iterator ite;13 for (ite = nums.begin(); ite != nums.end(); ite++){14 myMap.insert(map
                
                 ::value_type(*ite, ite - nums.begin()));15 }16 for (int i = 0; i < nums.size(); i++){17 myMap[nums[i]] = i;18 }19 for (int i = 0; i < nums.size(); i++){20 int a = nums[i];21 int b = target - a;22 if (myMap.count(b) != 0 && i != myMap[b]){23 res.push_back(i);24 res.push_back(myMap[b]);25 return res;26 }27 }28 }29 };

View Code

转载于:https://www.cnblogs.com/Elaine-DWL/p/8097944.html

你可能感兴趣的文章