剑指offer面试题41 和为s的俩个数字 vs 和为s的连续正数序列-题目

分析
第一道题目要求和为s的俩个数字,且数组是排序的,遇到这类排序的题目一定要往二分的思维上靠,我们可以先求最小值和最大值的和,且俩个指针分别指向最小值和最大值,如果和比s大那么最大值的指针减1,反之最小值的指针加1,这样通过o(n)的复杂度就可以拿到结果
第二道题目要求和为s的正数序列,这道题目思路是一样的,同样可以用俩个指针,分别指向元素为1和2开始,且最小元素的指针不能超过s的一半,因为超过一半就不是俩个数了。开始遍历的时候如果和比s小那么不断后移最大指针,当比s大的时候则后移最小指针

public class FortyOne {
	public static void main(String[] args) {
		int[] arr = {1,2,4,7,11,15};
		//findSum(arr,15);
		printSeq(15);
	}
	public static void printSeq(int data) {
		int start  = 1;
		int end = 2;
		int curSum = start + end;
		int middle = (1 + data) / 2;
		while(start < middle) {
			if(curSum == data) {
				for(int i = start;i<=end;i++) {
					System.out.print(i);
				}
				System.out.println();
			}
			while(curSum > data & start < middle) {
				curSum -= start;
				start++;
				if(curSum == data) {
					for(int i = start;i<=end;i++) {
						System.out.print(i);
					}
					System.out.println();
				}
			}
			end++;
			curSum+=end;
		}

	}
	public static void findSum(int[] arr,int k) {
		if(arr == null || arr.length <= 0) {
			return;
		}
		int start = 0;
		int end = arr.length - 1;
		while(start <= end) {
			int sum = arr[start] + arr[end];
			if(sum < k) {
				start  = start + 1;
			} else if (sum > k) {
				end = end - 1;
			} else {
				System.out.println(arr[start]);
				System.out.println(arr[end]);
				break;
			}
		}

	}
}
上一篇:【自动化】在WPF应用程序中使用MVVM框架实现Modbus协议通信


下一篇:力扣 739. 每日温度 & 496.下一个更大元素 I