《剑指offer》面试题41：和为s的两个数字 VS 和为s的连续正数序列和为s的两个数字和为s的连续正数序列

110 阅读 0 评论 73 点赞

我是靠谱客的博主虚拟翅膀，这篇文章主要介绍《剑指offer》面试题41：和为s的两个数字 VS 和为s的连续正数序列和为s的两个数字和为s的连续正数序列，现在分享给大家，希望可以做个参考。

和为s的两个数字

题目一：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，输出任意一对即可。

思路：由于是递增排序数组，所以考虑两个指针遍历，i 指针从头开始，j 指针从尾开始。如果 i 数和 j 数之和 > target，将 j 指针前移；如果小于target，将 i 指针后移。找到相等则return，找不到即(i=j-1 && [i]+[j]!=target)。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] FindNumWithSum(int[] nums, int target) {
	if (nums.length == 0 || nums == null)
		return null;
	int i = 0, j = nums.length-1;
	int[] res = new int[2];
	while (i < j) {
		if (nums[i]+nums[j] < target) {
			i ++;
		} else if (nums[i]+nums[j] > target) {
			j --;
		} else {
			res[0] = nums[i];
			res[1] = nums[j];
			return res;
		}
		System.out.println(nums[i] + " " + nums[j]);
	}
	return res;
}

和为s的连续正数序列

题目二：输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以结果打印出三个连续序列1~5、4~6和7~8。

思路：用s指针和e指针分别标记序列的头和尾，sum用来记录当前序列的和。e指针挨个向后移动，sum+=[e]，如果sum > target，s指针后移，sum-=[s]，直到 <= target。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void FindContiousSeq(int n, int target) {
	if (target == 0)
		System.out.println("0");
	int s = 1, e = 1;
	int sum = 0;
	while ((e<=n) && (s<=e)) {
		sum += e;
		while (sum > target) {
			sum -= s;
			s ++;
		}
		if (sum == target) {
			for (int i=s; i<=e; i++)
				System.out.print(i+" ");
			System.out.println("n");
		}
		e ++;
	}
}