leetcode 167. Two Sum II - Input array is sorted

2017-08-06

题意

在一个已知排好序的数组中寻找两个数加起来等于目标数。返回这两个数的下标

我的思路

假定数一为数组的第一个，依次遍历后续当大于了目标数就停下。等于了就返回。小于了就下一位。

我的代码

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int sub = target;
        int[] result = new int[2];
        for(int i=0;i<numbers.length;i++){
            sub = target-numbers[i];
            result[0] = i+1;                    
            for(int j=i+1;j<numbers.length;j++){
                if(numbers[j]>sub) break;
                if(numbers[j]==sub) {
                    result[1] = j+1;                    
                    return result;
                }
            }
        }
        return result;
    }
}

大神代码

分别从数组的开始和结尾，如果加起来大于目标数，尾下标减少，反之头下标增加。

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0 || numbers.length == 1 && numbers[0] != target) {
            return null;
        }
        int s = 0;
        int e = numbers.length - 1;
        while (s < e) {
            int m = numbers[s];
            int n = numbers[e];
            if (m + n > target) {
                e --;
            } else if (m + n < target) {
                s ++;
            } else {
                break;
            }
        }
        return new int[]{s + 1, e + 1};
    }
}