Solution 14: Two Sum

问题描述

输入一个升序排列的数组和一个数字。在数组中查找两个数，使得两个数之和等于指定的数。

如果存在多对，只需要输出其中一对即可。

解决思路

类似于快排中的partition函数。时间复杂度为O(n)。

程序

public class TwoSum {
	public List<Integer> getTwoNumOfSum(int[] nums, int sum) {
		List<Integer> res = new ArrayList<Integer>();
		if (nums == null || nums.length == 0) {
			return res;
		}

		int low = 0, high = nums.length - 1;
		while (low < high) {
			int cur = nums[low] + nums[high];
			if (cur == sum) {
				res.add(nums[low]);
				res.add(nums[high]);
				break;
			}
			if (cur < sum) {
				++low;
			} else {
				--high;
			}
		}

		return res;
	}
}