博客

题目:

• 给定一个升序排列好的整数数组num,从数组中找出两个数满足相加之和等于目标数target
• 假设每个输入只对应唯一的答案，而且不可以重复使用相同的元素
• 返回两数的下标，以数组的形式返回

可以采用两种方法:
①用一个Map来存放数组中的所有元素，遍历数组，用target-num[i]判断其值是否在map中，还需要判断两个值的下标是否相等，如果不相等则返回结果数组，否则返回null
②采用二分法来求解另外一个数，遍历数组，result=target-num[i],用二分法判断result中是否存在于数组中，如果存在，则返回结果数组,否则返回null。

代码:

package 两数之和_有序数组;

/**
 * @author:MrQ
 * @date 2021/7/30-10:27
 */

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class main {
    public static void main(String[] args) {
        int[] solution = solution(new int[]{1, 2, 3, 4, 5, 6, 8}, 12);
        if (solution==null){
            System.out.println("未找到对应下标");
        }else {
            System.out.println(solution[0]);
            System.out.println(solution[1]);
        }
        System.out.println("----------------------------------------");
        int[] solution01 = solution01(new int[]{1, 2, 3, 4, 5, 6, 8}, 12);
        if (solution01==null){
            System.out.println("未找到对应的下标");
        }else {
            System.out.println(solution01[0]);
            System.out.println(solution01[1]);
        }
    }

    /**
     * 和无序数组采用的方法相同，都用了一个map来存储数组中的元素
     * @param num
     * @param target
     * @return
     */
    static int[] solution(int []num,int target){
        Map<Integer,Integer> map = new HashMap<>();
        for (int i=0;i<num.length;i++){
            map.put(num[i],i);
        }
        for (int i=0;i<num.length;i++){
            int result = target-num[i];
            if (map.containsKey(result)){
                if (map.get(result)!=i){
                    return new int[]{i,map.get(result)};
                }
            }
        }
        return null;
    }
    public static int[] solution01(int []num,int target){
        for (int i=0;i< num.length;i++){
            int left=i+1,mid,right=num.length-1;
            int result=target-num[i];
            mid=(left+right)/2;
            //利用二分法查找出数组的元素
            while (left<=right) {
                if (num[mid] > result) {   //向左边寻找元素
                    right = mid - 1;
                    mid = (left+right)/2;
                }
                if (num[mid] < result) {   //向右边寻找元素
                    left = mid + 1;
                    mid = (left+right)/2;
                }
                if (num[mid] == result) {  //等于result
                    return new int[]{i, mid};
                }
            }
        }
        return null;
    }

}