1. 两数之和

佚名 7年前 (2019-04-24) 随笔 1471人围观抢沙发百度已收录

#include<iostream>
#include<stdio.h>
#include<vector>
#include <algorithm>
#include <functional>
#include<string>
#include<fstream>
#include <sstream>
#include <unordered_map>
using namespace std;
//构建解决方案
class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target)
	{
		unordered_map<int, int>m;//因此遇到查找问题，常会考虑一下用unordered_map构造空的容器
		vector<int>result;//定义输出结果向量
		for (int i = 0; i< nums.size(); i++)///* 遍历数组 */
		{
			if (m.find(nums[i]) == m.end())//若这个元素在m中,则判断当前的位置i与查找到的nums[i],得到其位置
			{
				m[target - nums[i]] = i;

			}
			else
			{
				result.push_back(m[nums[i]]);//获得下标值
				result.push_back(i);
				break;
			}
		}
		return result;
	}
};

void trimLeftTrailingSpaces(string &input) {
	input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) 
	{
		return !isspace(ch);
	}));
}

void trimRightTrailingSpaces(string &input) {
	input.erase(find_if(input.rbegin(), input.rend(), [](int ch) 
	{
		return !isspace(ch);
	}).base(), input.end());
}

vector<int> stringToIntegerVector(string input) {
	vector<int> output;
	trimLeftTrailingSpaces(input);
	trimRightTrailingSpaces(input);
	input = input.substr(1, input.length() - 2);
	stringstream ss;
	ss.str(input);
	string item;
	char delim = ',';
	while (getline(ss, item, delim)) {
		output.push_back(stoi(item));
	}
	return output;
}

int stringToInteger(string input)
{
	return stoi(input);
}
string integerVectorToString(vector<int> list, int length = -1) 
{
	if (length == -1) 
	{
		length = list.size();
	}

	if (length == 0) {
		return "[]";
	}
	string result;
	for (int index = 0; index < length; index++)
	{
		int number = list[index];
		result += to_string(number) + ", ";
	}
	return "[" + result.substr(0, result.length() - 2) + "]";
}
int main() {
	string line;
	while (getline(cin, line))
	{
		vector<int> nums = stringToIntegerVector(line);
		getline(cin, line);
		int target = stringToInteger(line);
		vector<int> ret = Solution().twoSum(nums, target);
		string out = integerVectorToString(ret);
		cout << out << endl;
	}
	return 0;
}