167. Two Sum II

Leetcode Array Two Pointers 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.

分析

一种最简单的方法和LeetCode 1 Two Sum一样,利用哈希表来处理。代码是一摸一样的。

public static int[] twoSum(int[] nums, int target) {
    if (nums == null || nums.length < 2) return new int[]{};
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i< nums.length; i++)
        if (map.containsKey(nums[i]))
            return new int[]{map.get(nums[i]), i};
        else map.put(target - nums[i], i); 
    return new int[]{};
}

另一种方法是利用两个指针,慢慢逼近所求值: 先在数组中选择两个数字

  • 如果它们的和等于输⼊的target,我们就找到了要找的两个数字。
  • 如果它们的和小于输入的target,为了减小和,可以选择前⾯的数字,因为排在数组前⾯的数字要⼩⼀些。
  • 如果它们的和大于输入的target,为了增加和,可以选择较⼩的数字后⾯的数字,因为排在后⾯的数字要⼤⼀些。
public int[] twoSumTwoPointers(int[] nums, int target) {
    int left = 0, right = nums - 1;
    while (nums[left] + nums[right] != target)
        if (nums[left] + nums[right] > target) right--;
        else left++;
    return new int[]{left + 1, right + 1};
}