LeetCode - Easy - 167. Two Sum II - Input array is sorted

ゝ一世哀愁。 2022-12-29 09:17 102阅读 0赞

## Topic ##

*  Array
 *  Two Pointers
 *  Binary Search

## Description ##

[https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/][https_leetcode.com_problems_two-sum-ii-input-array-is-sorted]

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

**Example 2**:

Input: numbers = [2,3,4], target = 6
    Output: [1,3]

**Example 3**:

Input: numbers = [-1,0], target = -1
    Output: [1,2]

**Constraints**:

*  2 <= nums.length <= 3 \* 10⁴
 *  \-1000 <= nums\[i\] <= 1000
 *  nums is sorted in increasing order.
 *  \-1000 <= target <= 1000

## Analysis ##

方法一：二分查找，我写的。

方法二：双指针。

方法三：二分查找，比方法一精简。

## Submission ##

public class TwoSumIIInputArrayIsSorted { 
    	// 方法一：我写的
    	public int[] twoSum1(int[] numbers, int target) { 
    		if (numbers == null || numbers.length == 0)
    			return null;
    
    		for (int i = 0; i < numbers.length; i++) { 
    
    			int diff = target - numbers[i];
    
    			int otherTargetIndex = -1;
    			if (diff < numbers[i]) { 
    				otherTargetIndex = binarySearch(numbers, 0, i - 1, diff);
    			} else { 
    				otherTargetIndex = binarySearch(numbers, i + 1, numbers.length - 1, diff);
    			}
    
    			if (otherTargetIndex != -1)
    				return new int[] {  Math.min(otherTargetIndex, i) + 1, Math.max(otherTargetIndex, i) + 1 };
    		}
    
    		return null;
    	}
    
    	private int binarySearch(int[] numbers, int left, int right, int value) { 
    		while (left <= right) { 
    			int mid = left + (right - left) / 2;
    
    			if (value < numbers[mid]) { 
    				right = mid - 1;
    			} else if (numbers[mid] < value) { 
    				left = mid + 1;
    			} else { 
    				return mid;
    			}
    
    		}
    		return -1;
    	}
    
    	// 方法二：双指针
    	public int[] twoSum2(int[] numbers, int target) { 
    		int first = 0, last = numbers.length - 1;
    		while (numbers[first] + numbers[last] != target) { 
    			if (numbers[first] + numbers[last] > target)
    				last--;
    			else
    				first++;
    		}
    		return new int[] {  first + 1, last + 1 };
    	}
    
    	// 方法三：
    	public int[] twoSum3(int[] numbers, int target) { 
    		if (numbers == null || numbers.length == 0)
    			return null;
    
    		for (int i = 0; i < numbers.length; i++) { 
    			
    			//在i后面查找，前面的不用管，这是与方法一的区别
    			int start = i + 1, 
    					end = numbers.length - 1, gap = target - numbers[i];
    			while (start <= end) { 
    				int m = start + (end - start) / 2;
    				if (numbers[m] == gap)
    					return new int[] {  i + 1, m + 1 };
    				else if (numbers[m] > gap)
    					end = m - 1;
    				else
    					start = m + 1;
    			}
    		}
    		return null;
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    public class TwoSumIIInputArrayIsSortedTest { 
    
    	@Test
    	public void test() { 
    		TwoSumIIInputArrayIsSorted obj = new TwoSumIIInputArrayIsSorted();
    
    		assertArrayEquals(new int[] { 1, 2},  obj.twoSum1(new int[] { 2, 7, 11, 15}, 9));
    		assertArrayEquals(new int[] { 1, 3},  obj.twoSum1(new int[] { 2, 3, 4}, 6));
    		assertArrayEquals(new int[] { 1, 2},  obj.twoSum1(new int[] { -1, 0}, -1));
    		
    		assertArrayEquals(new int[] { 1, 2},  obj.twoSum2(new int[] { 2, 7, 11, 15}, 9));
    		assertArrayEquals(new int[] { 1, 3},  obj.twoSum2(new int[] { 2, 3, 4}, 6));
    		assertArrayEquals(new int[] { 1, 2},  obj.twoSum2(new int[] { -1, 0}, -1));
    		
    		assertArrayEquals(new int[] { 1, 2},  obj.twoSum3(new int[] { 2, 7, 11, 15}, 9));
    		assertArrayEquals(new int[] { 1, 3},  obj.twoSum3(new int[] { 2, 3, 4}, 6));
    		assertArrayEquals(new int[] { 1, 2},  obj.twoSum3(new int[] { -1, 0}, -1));
    	}
    }

[https_leetcode.com_problems_two-sum-ii-input-array-is-sorted]: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/