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:

• 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.
```

#### 分析¶

```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};
}
```