LeetCode167. Two Sum II - Input array is sorted解答

拼搏现实的明天。 2022-06-07 10:57 129阅读 0赞

昨天因为课太多了，又忙着做系统级编程的作业，所以拖了一天都没做题，今天趁着上一个水课，先来把今天的目标完成。

# 先来看一下题目 #

> Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
> 
> The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
> 
> You may assume that each input would have exactly one solution and you may not use the same element twice.

题目的大意是：给你一个已经按照升序排好序的数组，要求你找到数组里的这两个数，这两个数加起来等于给定的数字。你的函数应该返回数组里这两个数的索引，第一个数的索引必须小于第二个数的索引，并且这两个数不能相同，题目保证每一个数组里面都有且仅有一对数字满足条件。

> Input: numbers=\{2, 7, 11, 15\}, target=9  
> Output: index1=1, index2=2

# 解题思路 #

这道题，它已经说了，给定的数组是按照升序排序好的，所以一定可以通过它的这个特点来设计算法，而且最好是只遍历一遍。  
我们从数组的两端开始遍历，每次用小的一端加上大的一端，如果这个值大于给定的数，说明大的那端比我们要找的数要大，所以大的一端往前移；如果这个值小于给定的数，说明小的那端比我们要找的小，所以小的一端往后面移。下面我用一张图来说明这个算法  
![这里写图片描述][SouthEast]  
由于这个数组是经过排序的，所以不必担心会忽略掉一些可能的答案。  
下面上代码

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

# 更好的算法 #

class Solution {
        public int[] twoSum(int[] numbers, int target) {
            if (numbers == null || numbers.length == 0) {
                return new int[2];
            }
            int start = 0;
            int end = numbers.length - 1;
            while (start < end) {
                if (numbers[start] + numbers[end] == target) {
                    return new int[]{start + 1, end + 1};
                } else if (numbers[start] + numbers[end] > target) {
                    // move end forward to the last value that numbers[end] <= target - numbers[start]
                    end = largestSmallerOrLastEqual(numbers, start, end, target - numbers[start]);
                } else {
                    // move start backword to the first value that numbers[start] >= target - numbers[end]
                    start = smallestLargerOrFirstEqual(numbers, start, end, target - numbers[end]);
                }
            }
            return new int[2];
        }
        private int largestSmallerOrLastEqual(int[] numbers, int start, int end, int target) {
            int left = start;
            int right = end;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (numbers[mid] > target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return right;
        }
        private int smallestLargerOrFirstEqual(int[] numbers, int start, int end, int target) {
            int left = start;
            int right = end;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (numbers[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return left;
        }
    }

这个代码比较长，基本思路还是从两端向中间遍历，不过在两个端点的移动算法方面有一些改进。

[SouthEast]: /images/20220607/b8b9c39200e6430e8872f22b7fbd9285.png