LeetCode题目1:Two Sum

嗯,这里是简介,主题配置内可以修改,如留空则不显示

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;
}




发表评论

必填

选填

选填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

Hello world. 豫ICP备16008819号-1.

Power by Z-BlogPHP  Theme by wzdaxue