力扣-167号题.两数之和II-输入有序的数组

目录

力扣-167号题.两数之和II-输入有序的数组

第一种解法：暴力解法

第二种解法：map

第三种解法：碰撞指针

代码实现

---

力扣-167号题.两数之和II-输入有序的数组

这道题并不难，但是我们要注意到他的下标是从1开始的整数组，而且已经是按非递减顺序排列的。并且返回的数组长度仅为2，每个输入只对应唯一一个答案，而且不可以重复使用相同的元素

第一种解法：暴力解法

/*
     * 暴力解法
     * */
    public int[] twoSum02(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0) {
            return null;
        }
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i+1; j < numbers.length; j++) {
                if (numbers[i]+numbers[j]==target){
                    return new int[]{i+1,j+1};
                }
            }
        }
        return null;
    }

ps：这里为什么返回的数组的下标要加1，是因为我们这里数组的下标是从0开始的，并且我们的循环也是从0开始的，所以要给最终的索引结果加1，后面的解法亦是如此

第二种解法：map

/*
     * 使用map
     *
     * */
    public int[] twoSum01(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0) {
            return null;
        }
        // KEY--->value  VALUE--->index
        HashMap map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            int sub = target - numbers[i];
            if (map.containsKey(sub)) {
                return new int[]{map.get(sub) + 1, i + 1};
            } else {
                map.put(numbers[i], i);
            }
        }
        return null;
    }

这里我们主要使用了一个减法的特性，通过去找目标数字的差值从而达到解决我们这个问题，同样返回的结果索引是要加1的

第三种解法：碰撞指针

这个方法并不难难理解，声明两个指针，一个在数组开始的位置，一个在数组的尾部

• 如果两个指针一开始的位置就是我们的目标值，我们直接返回其索引加1

• 如果相加大于我们的目标值，那就说明我们需要将右边的指针向左移动，因为这个数组是已经按照升序排列的，如果大的话，将右边指针向左移动才能减少其值

• 如果相加的值小于我们的目标值，那我们就将左边的指针向右移动

代码实现

/*
 * 碰撞指针
 * */
public int[] twoSum03(int[] numbers, int target) {
    if (numbers == null || numbers.length == 0) {
        return null;
    }
    // 声明指针(2)
    int i = 0;
    int j = numbers.length - 1;
    for (; i < j; ) {
        if (numbers[i] + numbers[j] == target) {
            return new int[]{i + 1, j + 1};
        } else if (numbers[i] + numbers[j] > target) {
            j--;
        } else {
            i++;
        }
    }
    return null;
}