数组与字符串13-两数之和等于目标数

两数之和等于目标数

一 题目
源自leetcode

给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

提示：你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
二 解题
可以使用暴力破解来求此题。对于numbers为[2,7,11,15]，元素不重复的两数有：(2,7), (2,11), (2,15), (7,11), (7,15), (11,15).由于要求1 <= answer[0] < answer[1] <= numbers.length ，因此两个数我们按从小到大的顺序来写。其中，因为numbers为非递减顺序排列，所以结果能取到的最大值为target-numbers[0]，因为numbers[0]为最小的值。
代码：

class Solution {
    
    public int[] twoSum(int[] numbers, int target) {
    
        int[] result = new int[2];
        int max = target - numbers[0];
        boolean flag = false;
        for(int i =0;i<numbers.length-1;i++){
    
            for(int j = i+1;j< numbers.length;j++){
    
                if(numbers[j]>max){
    
                    break;
                }else if(numbers[i]+numbers[j]==target){
    
                		//题目要求index从1开始
                    result[0]=i+1;
                    result[1]=j+1;
                    flag=true;
                    break;
                }
            }
            if(flag){
    
                break;
            }
        }
        return result;
    }
}

三 优化
可以使用双指针来简化操作，使用两个指针left与right，初始化时left=0，指向最小值，right=numbers.length-1，指向最大值。由于数组为非递减顺序排列，所以当numbers[left]+numbers[right]>target时，right–，找更小的值。numbers[left]+numbers[right]<target时，left++，找更大的值。

class Solution {
    
    public int[] twoSum(int[] numbers, int target) {
    
        int left = 0,right = numbers.length-1;
        while (left<right){
    
            if(numbers[left]+numbers[right]==target){
    
                return new int[]{
    left+1,right+1};
            }else if(numbers[left]+numbers[right]>target){
    
                right--;
            }else{
    
                left++;
            }
        }
        return new int[]{
    -1,-1};
    }
}