LeetCode: Two Sum

坑爹的多数次过。。

 1 class Solution {
 2 public:
 3     vector<int> twoSum(vector<int> &numbers, int target) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         int left = 0;
 7         int right = numbers.size() - 1;
 8         vector<int> ret;
 9         map<int, vector<int>> S;
10         for (int i = 0; i < numbers.size(); i++) S[numbers[i]].push_back(i+1);
11         sort(numbers.begin(), numbers.end());
12         while (left < right) {
13             if (numbers[left] + numbers[right] == target) {
14                 if (S[numbers[left]].size() > 1) {
15                     ret.push_back(S[numbers[left]][0]);
16                     ret.push_back(S[numbers[right]][1]);
17                     return ret;
18                 }
19                 int a = S[numbers[left]][0];
20                 int b = S[numbers[right]][0];
21                 if (a > b) {
22                     ret.push_back(b);
23                     ret.push_back(a);
24                 }
25                 else {
26                     ret.push_back(a);
27                     ret.push_back(b);
28                 }
29                 return ret;
30             }
31             if (numbers[left] + numbers[right] < target) left++;
32             else right--;
33         }
34     }
35 };

后来写了另外一段代码，更清楚点

 1 class Solution {
 2 public:
 3     vector<int> twoSum(vector<int> &numbers, int target) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         map<int, int> S;
 7         for (int i = 0; i < numbers.size(); i++) S[i+1] = numbers[i];
 8         sort(numbers.begin(), numbers.end());
 9         int left = 0;
10         int right = numbers.size()-1;
11         while (left < right) {
12             int sum = numbers[left] + numbers[right];
13             if (sum == target) break;
14             if (sum < target) left++;
15             else right--;
16         }
17         vector<int> ret;
18         int first, second;
19         first = second = 0;
20         for (map<int, int>::iterator it = S.begin(); it != S.end(); it++) {
21             if (numbers[left] == it->second || numbers[right] == it->second) {
22                 if (!first) first = it->first;
23                 else second = it->first;
24             }
25         }
26         if (first > second) swap(first, second);
27         ret.push_back(first);
28         ret.push_back(second);
29         return ret;
30     }
31 };

 1 public class Solution {
 2     public int[] TwoSum(int[] nums, int target) {
 3         Dictionary<int, int> S = new Dictionary<int, int>();
 4         for (int i = 0; i < nums.Length; i++) S.Add(i+1, nums[i]);
 5         Array.Sort(nums);
 6         int left = 0, right = nums.Length-1;
 7         while (left < right) {
 8             int sum = nums[left] + nums[right];
 9             if (sum == target) break;
10             if (sum < target) left++;
11             else right--;
12         }
13         int[] ans = new int[2];
14         int first = 0, second = 0;
15         foreach (var v in S) {
16             if (nums[left] == v.Value || nums[right] == v.Value) {
17                 if (first == 0) first = v.Key;
18                 else second = v.Key;
19             }
20         }
21         if (first > second) {
22             int tmp = first;
23             first = second;
24             second = tmp;
25         }
26         ans[0] = first;
27         ans[1] = second;
28         return ans;
29     }
30 }

View Code