题目
给一个整数数组,找到两个数使得他们的和等于一个给定的数 target。
你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 1 到 n,不是以 0 开头。http://www.lintcode.com/zh-cn/problem/two-sum/
分析
由于这样的组合必然存在,那么两重循环即可找到数组的下标,这是最简单直白的答案。还有一种变种优化方案,就是将数组做一个排序,由于结果要求返回的是原来数组中的下标,因此还需要将排序的结果与原来的结果序号绑定对应,然后再按照数值大小排序。
代码
public class Solution {
/*
* @param numbers: An array of Integer
* @param target: target = numbers[index1] + numbers[index2]
* @return: [index1 + 1, index2 + 1] (index1 < index2)
*/
public int[] twoSum(int[] numbers, int target) {
// write your code here
int i, j;
i = j = 0;
outer:for(i=0; i< numbers.length-1; i++){
for(j=i+1; j< numbers.length; j++){
if(numbers[i] + numbers[j] == target){
break outer;
}
}
}
return new int[]{i+1, j+1};
}
}