【LeetCode】001. TwoSum

题目：

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 = [, , , ], target = ,

Because nums[] + nums[] =  +  = ,

return [, ].

题解：

　　首先想到暴力解，TLE(Time Limit Exceeded)问题先不考虑。从数组头开始，依次与其他元素比较，然后向后移动开始位置，需要注意的是返回的位置是从0开始的

Solution 1 （TLE）

 class Solution {

 public:

     vector<int> twoSum(vector<int> &numbers, int target) {

         vector<int> result;

         int n = numbers.size();

         for (int i = ; i < n; i++) {

             for (int j = i + ; j < n; j++) {

                 if (numbers[i] + numbers[j] == target) {

                     result.push_back(i);

                     result.push_back(j);

                 }

             }

         }

         return result;

     }

 };

　　那怎样才能降低时间复杂度呢？这里有个经验准则，数组及字符串问题往往与(unordered)map、(unordered)set有关。这里使用unordered_map，用于查找；首先想到的思路是先遍历一遍数组，建立map映射表（元素值和位置的映射），然后再遍历一遍查找与当前元素之和为目标值的元素。建立m(数组元素)与m的位置的映射。

Solution 2

 class Solution {

 public:

     vector<int> twoSum(vector<int>& nums, int target) {

         unordered_map<int, int> m;

         int n = nums.size();

         vector<int> result;

         for (int i = ; i < n; ++i) {

             m[nums[i]] = i;

         }

         for (int i = ; i < n; ++i) {

             int t = target - nums[i];

             //m.find(t) != m.end() 可以用 m.count(t)代替

 　　　　　　　//you may not use the same element twice.

             if (m.find(t) != m.end() && m[t] != i) {

                 result.push_back(i);

                 result.push_back(m[t]);

                 break;

             }

         }

         return result;

     }

 };

　　有一种优化方法，思路是从数组头开始，依次将元素对应的加数加入map中，在建立映射的过程中，若发现map中已经存在了一个元素，由于这个元素的存在是之前的操作才加入到map中，及此元素对应的加数在之前已经存在，故直接返回即可。题设 each input would have exactly one solution。建立target-m与m的位置的映射。

Solution 3

 class Solution {

 public:

     vector<int> twoSum(vector<int>& nums, int target) {

         unordered_map<int, int> m;

         vector<int> result;

         for(int i=; i<nums.size(); i++)

         {

             if (m.find(nums[i])==m.end() )

             {

                 m[target - nums[i]] = i;

             }

             else

             {

                 result.push_back(m[nums[i]]);

                 result.push_back(i);

                 break;

             }

         }

         return result;

     }

 };

巴特西

【LeetCode】001. TwoSum

最新文章

热门文章