`
betakoli
  • 浏览: 166184 次
社区版块
存档分类
最新评论

LeetCode 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

题意:在数组中找出两个数,使得之和为target。给出这两个数在数组中的坐标,注意坐标下标开始为1.

题目地址:https://oj.leetcode.com/problems/two-sum/

解题思路:使用map,将所有的数存放其中,然后遍历数组,在map中找另外一个数与当前数相加等于目标值。

public int[] twoSum(int[] numbers, int target) {
		Map<Integer,Integer> map = new HashMap<Integer,Integer>();
		for(int i=0;i<numbers.length;i++)
			map.put(numbers[i], i);
		boolean b =false;
		int j=0;
		int n=0;
		for(j=0;j<numbers.length;j++)
		{
			int a = target-numbers[j];
			b = map.containsKey(a);
			if(b)
			{
				n=map.get(a);
//判断不为当前数的下标
				if(n!=j)
					break;
			}
		}
		if(b)
		{
			if(n>j)
			{
				int a[] = {j+1,n+1};
				return a;
			}else 
			{
				int a[] = {n+1,j+1};
				return a;
			}
		}else 
		{
			return null;
		}
	}

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics