Hello world. 志不强者智不达,言不信者行不果.

LeetCode题目1:Two Sum

链接地址:https://leetcode.com/problems/two-sum/

原题:

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

题目的意思:给出一串数字,找出其中两个数字为指定数值的两个数在数字串中的位置。

思路:先排序,然后设置两个指针左右移动即可。

扩展:思考到三个数(多个数字)相加呢?两个数相乘或相除等操作。

参考代码:(附带此时程序)

C++:

#include <iostream.h>
#include <map>
#include <malloc.h>
#include <stdio.h>  
#include <stdlib.h> 
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

void print(int elem){cout<<elem<<' ';};

struct pare{
	int value;
	int key;
};

bool comp(const pare &l,  const pare &r)
{
	return l.value<r.value;
};

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
		/* sort vector */
		vector<pare> num;
		for(int i=0; i<numbers.size(); i++)
		{
			pare p;
			p.value = numbers[i];
			p.key = i+1;
			num.push_back(p);
		}

		/*
		for (i=0; i<numbers.size(); i++)
		{
			cout<<num[i].key<<" "<<num[i].value<<endl;
		}*/

		sort(num.begin(), num.end(), comp);
		/*
		for (i=0; i<numbers.size(); i++)
		{
			cout<<num[i].key<<" "<<num[i].value<<endl;
		}*/

		vector<pare>::iterator l = num.begin();
		vector<pare>::iterator r = num.end()-1;

		for(; l<r;)
		{
			if (l->value + r->value == target)
			{
				break;
			}else if (l->value + r->value > target)
			{
				r--;
			}else if (l->value + r->value < target)
			{
				l++;
			}
		}

		vector<int> result;
		result.push_back(l->key<r->key?l->key:r->key);
		result.push_back(l->key<r->key?r->key:l->key);
		//for_each(result.begin(), result.end(), print);
		return result;

    }
};

void main()
{
	vector<int> numbers;
	numbers.push_back(-1);
	numbers.push_back(-2);
	numbers.push_back(-3);
	numbers.push_back(-4);
	numbers.push_back(-5);

	//for_each(numbers.begin(), numbers.end(), print);

	Solution *s = new Solution;
	s->twoSum(numbers,-8);

	return;
}




标签: LeetcodeC++C

作者:yuanmouren1hao 分类:LeetCode 浏览:541 评论:0
留言列表
发表评论
来宾的头像

Top