题目

给一个整数数组，找到两个数使得他们的和等于一个给定的数 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};
    }
}