深入连续整数固定和之一 问题介绍及经典解法

在冼镜光的《c语言名题精选百则》中，问题2.16为连续整数固定和问题。

问题描述：
编写一个程序，读入一个正整数，把所有连续的，和为给定的正整数的正整数找出来。解中不包含该给定的正整数本身。

书中给出的givenSum1的code如下：

	private static void givenSum1(int given) {
		int left, right;
		int sum;

		for (sum = 0, left = right = 1; left < given / 2 + 1; right++) {
			sum += right;
			while (sum > given) {
				sum -= left;
				left++;
			}
			if (sum == given) {
				System.out.printf("\n%d - %d", left, right);
			}
		}
	}

分析：
通过简单的分析可以看出，该算法的复杂度为O(N)。

深入连续整数固定和之二  对问题的思考
http://zhang-xzhi-xjtu.iteye.com/blog/478941
深入连续整数固定和之三  新的算法
http://zhang-xzhi-xjtu.iteye.com/blog/479830

评论

1 楼 lzxz1234 2011-02-28  

貌似没问题，不过在Integer.MAX_VALUE的时候就死循环了