[LeetCode] Two Sum

问题:找出数组中两个数之和等于一个给定目标数。并输出这两个数在数组中的下标。

1.暴力O(n^2),两个for循环查找,TLE。

[LeetCode] Two Sum
 1 class Solution {
 2 public:
 3     vector<int> twoSum(vector<int> &numbers, int target) {
 4   
 5         vector<int> ans;
 6         for (int i = 0; i < numbers.size()-1; i++)
 7         {
 8             for (int j = i+1; j < numbers.size(); j++)
 9             {
10                 if (numbers[i] + numbers[j] == target)
11                 {
12                     ans.push_back(i+1);
13                     ans.push_back(j+1);
14                     return ans;
15                 }
16             }
17         }
18     }
19 };
[LeetCode] Two Sum

2.O(n*logn),用一个pair,记录index和num,然后排序num,用两个指针向中间移动寻找答案

如果 sum = l.num + r.num, 那么 l.index 和 r.index 就是答案。注意答案index的顺序。

[LeetCode] Two Sum
 1 int cmp(const pair<int, int> &a, const pair<int, int> &b) {
 2      if (a.first == b.first)     return a.second < b.second;
 3      else return a.first < b.first;
 4 }
 5  
 6 class Solution {
 7 public:
 8  
 9      vector<int> twoSum(vector<int> &numbers, int target) {
10      
11           assert(numbers.size() >= 2);
12  
13           vector<int> ans;
14           vector< pair<int, int> > PairNumber;
15           for (int i = 0; i < numbers.size(); i++) {
16                PairNumber.push_back(make_pair(numbers[i], i+1));
17           }
18  
19           sort(PairNumber.begin(), PairNumber.end(), cmp);
20  
21           int l = 0, r = PairNumber.size()-1;
22           while (l < r) {
23                int sum = PairNumber[l].first + PairNumber[r].first;
24                if (sum == target) {
25                     ans.push_back(min(PairNumber[l].second, PairNumber[r].second));
26                     ans.push_back(max(PairNumber[l].second, PairNumber[r].second));
27                     break;
28                }
29                else if (sum < target) {
30                     l++;
31                }
32                else {
33                     r--;
34                }
35           }
36           return ans;
37      }
38 };
[LeetCode] Two Sum

3.O(n),用hash来做。C++中使用map,O(nlogn)。在边进行hash当前数numbers[i]的时候边判断是否出现target-numbers[i]。

C++:

[LeetCode] Two Sum
 1 class Solution {
 2 public:
 3  
 4      vector<int> twoSum(vector<int> &numbers, int target) {
 5      
 6           vector<int> ans;
 7           map<int, int> hash;
 8           for (int i = 0; i < numbers.size(); ++i) {
 9                if (hash.find(target-numbers[i]) != hash.end()) {
10                     ans.push_back(hash[target-numbers[i]]);
11                     ans.push_back(i+1);
12                     break;
13                }
14                else {
15                     hash.insert(make_pair(numbers[i], i+1));
16                }
17                
18           }
19           return ans;
20      }
21 };
[LeetCode] Two Sum

Java:

[LeetCode] Two Sum
 1 import java.util.Hashtable;
 2 public class Solution {
 3      public int[] twoSum(int[] numbers, int target) {
 4           assert (numbers.length >= 2);
 5           int ans[] = new int[2];
 6           Hashtable<Integer, Integer> hash= new Hashtable<Integer, Integer>();
 7           for (int i = 0; i < numbers.length; i++) {
 8                if (hash.get(target-numbers[i]) != null) {
 9                     ans[0] = hash.get(target-numbers[i]);
10                     ans[1] = i+1;
11                     break;
12                }
13                else {
14                     hash.put(numbers[i], i+1);
15                }
16           }
17           return ans;
18      }
19 }
[LeetCode] Two Sum

[LeetCode] Two Sum

上一篇:增加鼠标右键_新建批处理


下一篇:计蒜客 踏青 dfs