LintCode 608 · Two Sum II - Input array is sorted.java

	public class Solution {
	/**
	* @param nums: an array of Integer
	* @param target: target = nums[index1] + nums[index2]
	* @return: [index1 + 1, index2 + 1] (index1 < index2)
	*/
	public int[] twoSum(int[] nums, int target) {
	// two pointers, O(n)/ Opposite Direction Two Pointers/ Alternatively you can solve with Hash Table.
	// handle corner cases
	if (nums == null || nums.length < 2) {
	return new int[]{0, 0};
	}
	// two pointers
	int left = 0, right = nums.length - 1;
	while (left + 1 < right) {
	if (nums[left] + nums[right] == target) {
	return new int[]{left + 1, right + 1};
	}
	if (nums[left] + nums[right] < target) {
	left++;
	} else {
	right--;
	}
	}
	if (nums[left] + nums[right] == target) {
	return new int[]{left + 1, right + 1};
	}
	// the returns are NOT 0-based。
	return new int[]{0, 0};
	}
	}

view raw LintCode 608 · Two Sum II - Input array is sorted.java hosted with ❤ by GitHub