Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/167.html

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

 

Example 1:

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. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

 

Constraints:

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

Algorithm

We only need two pointers, one pointing to the beginning, one pointing to the end, and then traversing toward the middle.

• If the two numbers pointed to are exactly equal to the target, the position of the two pointers can be directly returned.
• If it is less than the target, the left pointer is right. Move one bit, if greater than target, the right pointer moves one bit to the left, and so on until the two pointers meet and stop

Code

• Java
• Python
• C++
• Go
• TypeScript
• Javascript
• RenderScript

• public class Two_Sum_II_Input_array_is_sorted {
  
      // time: O(N)
      // space: O(1)
      class Solution {
          public int[] twoSum(int[] numbers, int target) {
              int i = 0, j = numbers.length-1;
              int sum;
              while (i < j) {
                  sum = numbers[i] + numbers[j];
                  if (sum == target)
                      return new int[]{i+1, j+1};
                  else if (sum < target)
                      i++;
                  else
                      j--;
              }
  
              return null;
  
          }
      }
  }
  
  
  ############
  
  class Solution {
      public int[] twoSum(int[] numbers, int target) {
          int i = 1, j = numbers.length;
          while (i < j) {
              int x = numbers[i - 1] + numbers[j - 1];
              if (x == target) {
                  return new int[] {i, j};
              }
              if (x < target) {
                  ++i;
              } else {
                  --j;
              }
          }
          return new int[] {-1, -1};
      }
  }
  

• class Solution:
      def twoSum(self, numbers: List[int], target: int) -> List[int]:
          i, j = 1, len(numbers)
          while i < j:
              x = numbers[i - 1] + numbers[j - 1]
              if x == target:
                  return [i, j]
              if x < target:
                  i += 1
              else:
                  j -= 1
          return [-1, -1]
  
  ############
  
  class Solution(object):
    def twoSum(self, nums, target):
      """
      :type numbers: List[int]
      :type target: int
      :rtype: List[int]
      """
      start, end = 0, len(nums) - 1
      while start < end:
        s = nums[start] + nums[end]
        if s > target:
          end -= 1
        elif s < target:
          start += 1
        else:
          return (start + 1, end + 1)
  
  

• class Solution {
  public:
      vector<int> twoSum(vector<int>& numbers, int target) {
          int left = 1, right = numbers.size();
          while (left < right) {
              int x = numbers[left - 1] + numbers[right - 1];
              if (x == target) return {left, right};
              if (x < target)
                  ++left;
              else
                  --right;
          }
          return {-1, -1};
      }
  };
  

• func twoSum(numbers []int, target int) []int {
  	i, j := 1, len(numbers)
  	for i < j {
  		x := numbers[i-1] + numbers[j-1]
  		if x == target {
  			return []int{i, j}
  		}
  		if x < target {
  			i++
  		} else {
  			j--
  		}
  	}
  	return []int{-1, -1}
  }
  

• function twoSum(numbers: number[], target: number): number[] {
      let i = 1,
          j = numbers.length;
      while (i < j) {
          const x = numbers[i - 1] + numbers[j - 1];
          if (x == target) {
              return [i, j];
          }
          if (x < target) {
              ++i;
          } else {
              --j;
          }
      }
      return [-1, -1];
  }
  
  

• /**
   * @param {number[]} numbers
   * @param {number} target
   * @return {number[]}
   */
  var twoSum = function (numbers, target) {
      let i = 1,
          j = numbers.length;
      while (i < j) {
          const x = numbers[i - 1] + numbers[j - 1];
          if (x == target) {
              return [i, j];
          }
          if (x < target) {
              ++i;
          } else {
              --j;
          }
      }
      return [-1, -1];
  };
  
  

• use std::cmp::Ordering;
  
  impl Solution {
      pub fn two_sum(numbers: Vec<i32>, target: i32) -> Vec<i32> {
          let n = numbers.len();
          let mut l = 0;
          let mut r = n - 1;
          loop {
              match (numbers[l] + numbers[r]).cmp(&target) {
                  Ordering::Less => l += 1,
                  Ordering::Greater => r -= 1,
                  Ordering::Equal => break,
              }
          }
          vec![l as i32 + 1, r as i32 + 1]
      }
  }
  
  

All Problems

All Solutions