分析
第一道题目要求和为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;
}
}
}
}