# [LeetCode] Two Sum II - Input array is sorted

Problem Description:

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.

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

The idea is very simple: set two pointers, one starts from l = 0 and the other starts from r = numbers.size() - 1. If the numbers pointed by them sum to target, we are done. Otherwise, if the their sum is larger than target, we know the number pointed by r is larger and so decrease r by 1. The case is similar if their sum is smaller than target (increase l by 1).

So we could write down the following code.

 1 class Solution {
2 public:
3     vector<int> twoSum(vector<int>& numbers, int target) {
4         int n = numbers.size(), l = 0, r = n - 1;
5         while (true) {
6             if (numbers[l] + numbers[r] == target)
7                 return {l + 1, r + 1};
8             if (numbers[l] + numbers[r] > target) r--;
9             else l++;
10         }
11     }
12 };

List strem sum
List strem sum
35 0
|
9月前
Leetcode Find Minimum in Rotated Sorted Array 题解

32 0
|

LeetCode 410. Split Array Largest Sum

122 0
LeetCode 307. Range Sum Query - Mutable
update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。
88 0
LeetCode 108. Convert Sorted Array to BST

59 0
|

LeetCode 81. Search in Rotated Sorted Array II

74 0
LeetCode之Two Sum II - Input array is sorted
LeetCode之Two Sum II - Input array is sorted
91 0
|

LeetCode之Find All Numbers Disappeared in an Array
LeetCode之Find All Numbers Disappeared in an Array
86 0
LeetCode 167：两数之和 II - 输入有序数组 Two Sum II - Input array is sorted

954 0