167. Two Sum II - Input array is sorted.md

167.Two Sum II - Input array is sorted

---

leetcode-cn Daily Challenge on July 20, 2020.

---

Difficulty : Easy

Related Topics : Array、Two Pinters、Binary Search

---

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.

---

Solution

• mine
  • Java
    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.6 MB, less than 42.35% of Java online submissions

      // O(N)time
      // O(1)space
      public int[] twoSum(int[] numbers, int target) {
          int s = 0, e = numbers.length - 1;
          while (s < e) {
              int sum = numbers[s] + numbers[e];
              if (sum > target) {
                  e--;
              } else if (sum < target) {
                  s++;
              } else {
                  return new int[]{s + 1, e + 1};
              }
          }
          return null;
      }
      

---

• the most votes
  • Runtime: 0 ms, faster than 100.00%, Memory Usage: 39.6 MB, less than 42.35% of Java online submissions

    // N = numbers.length  O(N)time  O(1)space
    public int[] twoSum(int[] num, int target) {
        int[] indice = new int[2];
        if (num == null || num.length < 2) return indice;
        int left = 0, right = num.length - 1;
        while (left < right) {
            int v = num[left] + num[right];
            if (v == target) {
                indice[0] = left + 1;
                indice[1] = right + 1;
                break;
            } else if (v > target) {
                right --;
            } else {
                left ++;
            }
        }
        return indice;
    }
    

---