LeetCode 167. Two Sum II - Input array is sorted (Java版; Easy)

古城微笑少年丶 2023-07-04 06:13 88阅读 0赞

### [welcome to my blog][] ###

## LeetCode 167. Two Sum II - Input array is sorted (Java版; Easy) ##

#### 题目描述 ####

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.
    
    Note:
    
    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.
    Example:
    
    Input: numbers = [2,7,11,15], target = 9
    Output: [1,2]
    Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

#### 第一次做; 双指针, 从两端向中间; 是否需要考虑 numbers\[left\] + numbers\[right\] 溢出？不需要。因为存在唯一解，所以即使溢出也能得到答案 ####

/* 双指针, 从两端向中间 */
    class Solution { 
        public int[] twoSum(int[] numbers, int target) { 
            int n=numbers.length, left=0, right=n-1;
            while(left<right){ 
                int sum = numbers[left] + numbers[right];
                if(sum > target){ 
                    right--;
                }
                else if(sum < target){ 
                    left++;
                }
                else
                    break;
            }
            return new int[]{ left+1, right+1};
        }
    }

#### [双指针压缩搜索空间的原理][Link 1] ####

![format_png][]

[welcome to my blog]: https://littlehaes.com
[Link 1]: https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/solution/yi-zhang-tu-gao-su-ni-on-de-shuang-zhi-zhen-jie-fa/
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS9mNzhjMjY5Njc3Njg4MTkxMDMwYTdhNTA1MTEzMjI0Mi94bWxub3RlLzBBRUFDNDhGQjg4QTRDNjA5QTI2QjM0Q0REQThCMTk2LzU4NzEz?x-oss-process=image/format,png