LeetCode -剑指offer II 006 - 排序数组中的两个数字之和 - Java

x33g5p2x  于2021-12-21 转载在 Java  
字(1.6k)|赞(0)|评价(0)|浏览(217)

题目

我来总结题目的意思; 给我们一个已将排好序的数组(升序:从低到高),再给我们一个整型数据,要我们从 该数组中找到两个元素的和 等于 这个整形数据,而且 这两个元素必须两个不同的元素。

解题思维一

首先我们知道了数组是升序(元素从左往右,从小到大),也就意味 如果 数组中的两个元素之和 大于 target,只需要 要 右边大的元素的下标后退一步(左边的元素 肯定比 右边的小),同理,如果 两个元素之和 小于 target,只需要 让左边元素的下标前进一位,因为右边的元素 比 左边大。

鉴于这想法上,我们创建 两个 整形变量 left 和 right,分别指向 数组 开头 和 结尾。

代码

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right =  numbers.length -1;// 下标 从 0 开始,以 元素个数减一 下标 为结尾。
        while(left< right){
            int sum = numbers[left] + numbers[right];
            if(sum == target){
                return new int[]{left,right};
            }else if(sum < target){
                left++;
            }else{
                right--;
            }
        }
        return null;// 没找就返回 一个 null
    }
}

解题思维二(在思维一的基础上,加入一个 二分法)

代码

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int len = numbers.length;
        for(int i = 0;i < len;i++ ){
            int left = i+1;
            int right = len - 1;
            while(left <= right){
                int mid =  left + (int)Math.floor((right - left)/2);
                // Math.floor 向下取整在取中间下标是,有可能是 0,再加上 此时的left 也是可以作为第二个下标元素。 
                // right - left)/2 是为了确保 得出下标 不超过 数组长度,是因为前面还有一个 left,防止加上它导致越界异常
                
                int sum = numbers[i]+numbers[mid];
                if(sum == target){
                     return new int[]{i,mid};
                }else if(sum < target){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }
        return null;
    }
}

解析

二分法 其实就是 二分查找。
我们的做法是这样的:把第一种解法程序中,加一个 for 循环遍历数组,
这样做,是由于题目要求 数组中 两个元素之和 等于 target ,其两个下标必须不同
所以,我们通过for循环变量,就能 得到 一个下标元素,
另外 left 和 right 创建方式和位置,都需要做出改变,left 等于此时 for的 循环变量 +1.,right 不变。

再把方法一中 while循环放入for循环中 左右指针定义的后面。(注意判断条件,要加上一个等号,因为此时是在 left 和 right 之间选取第二个下标元素,不存在第一个元素下标 和 第二个元素的下标相同的问题)
与原先while循环里的内容,不同的是 多出一个 记录 left 和 right 中间下标的变量
重点:
1、 计算 两个下标的元素 之和 : int sum =numbers[ i ] + numbers[ mid ]
i 是我们通过for循环变量,获得的第一个元素的下标, mid 是我们 通过 目前的 left 和 right 得到的中间下标元素 / 第二个下标元素
2、判断 :
如果 sum < tatget, left = mid + 1,因为,想要获得 更大的第二位下标元素,下标肯定是大于mid的,
sum > tatget 也是同理, right = mid -1;想要获得 更小的第二位下标元素,下标肯定是小于mid的
满足条件 就返回 i 和 mid 。

相关文章

微信公众号

最新文章

更多