首页 > 代码库 > 1. Two Sum

1. Two Sum

2024-09-04 21:10:09   215人阅读

题目：

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].

思路：

1.使用multimap存储元素和对应下标

2.对数组进行排序

3.从数组两端寻找目标元素

4.从multimap中查找对应下标

 

代码：

 1 class Solution {
 2 public:
 3     vector<int> twoSum(vector<int>& nums, int target) {
 4         int l = 0;
 5         int r = nums.size() - 1;
 6         int i = 0;
 7         vector<int> result;
 8         multimap<int, int> m;
 9         multimap<int, int>::iterator itmulti;
10         for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++) {
11             int temp = *it;
12             m.insert(make_pair(temp, i++));
13         }
14         sort(nums.begin(), nums.end());
15         while (l < r) {
16             if (nums[l] + nums[r] == target) {
17                 if (nums[l] == nums[r]) {
18                     for (itmulti = m.equal_range(nums[l]).first;
19                             itmulti != m.equal_range(nums[l]).second;
20                             itmulti++) {
21                         result.push_back((*itmulti).second);
22                     }
23                 } else {
24                     itmulti = m.equal_range(nums[l]).first;
25                     result.push_back((*itmulti).second);
26                     itmulti = m.equal_range(nums[r]).first;
27                     result.push_back((*itmulti).second);
28                 }
29                 break;
30             } else if (nums[l] + nums[r] < target) {
31                 l++;
32             } else {
33                 r--;
34             }
35         }
36         return result;
37     }
38 };

 

1. Two Sum


联系
我们