和为s 的两个数字vs 和为s 的连续正数序列
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> returnList = new ArrayList<>();
if(array == null || array.length ==0){
return returnList;
}
int start =0;
int end = array.length-1;
while(start < end){
if(array[start] + array[end]>sum){
end--;
}else if(array[start] + array[end]<sum){
start++;
}else{
returnList.add(array[start]);
returnList.add(array[end]);
break;
}
}
return returnList;
}
}import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> returnList = new ArrayList<>();
ArrayList<Integer> lists = new ArrayList<>();
if(sum < 3){
return returnList;
}
int start =1;
int end =2;
int numSum =0;
while(start !=(sum+1)/2){
numSum = SumFind(start,end);
if(numSum == sum){
for (int i = start; i <= end; i++) {
lists.add(i);
}
returnList.add(new ArrayList<>(lists));
lists.clear();
end++;
}else if(numSum > sum){
start++;
}else {
end ++;
}
}
return returnList;
}
private int SumFind(int start, int end) {
int sum =0;
for (int i = start; i <=end ; i++) {
sum+=i;
}
return sum;
}
}题目一 和为s 的两个数字
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
思路
对于一个数组，我们可以定义两个指针，一个从左往右遍历（pleft），另一个从右往左遍历（pright）。首先，我们比较第一个数字和最后一个数字的和curSum与给定数字sum，如果curSum < sum，那么我们就要加大输入值，所以，pleft向右移动一位，重复之前的计算；如果curSum > sum，那么我们就要减小输入值，所以，pright向左移动一位，重复之前的计算；如果相等，那么这两个数字就是我们要找的数字，直接输出即可。
这么做的好处是，也保证了乘积最小。
代码
public class findNumbersWithSum {
public static void main(String[] args) {
int[] nums = {1,2,4,7,11,15};
int target = 15;
System.out.println(findNumbersWithSum(nums,target));
}
public static boolean findNumbersWithSum(int[] nums,int target){
if(nums == null || nums.length == 0){
return false;
}
int start = 0;
int end = nums.length-1;
while (start < end){
if((nums[start] + nums[end]) > target){
--end;
}else if((nums[start] + nums[end]) < target){
++start;
}else {
System.out.println(start +" "+ end + " "+nums[start] + " "+nums[end]);
return true;
}
}
return false;
}
}
规范代码
/**
* 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得得它们的和正好是s。
* 如果有多对数字的和等于s，输出任意一对即可。
*
* @param data
* @param sum
* @return
*/
public static List<Integer> findNumbersWithSum(int[] data, int sum) {
List<Integer> result = new ArrayList<>(2);
if (data == null || data.length < 2) {
return result;
}
int ahead = data.length - 1;
int behind = 0;
long curSum; // 统计和，取long是防止结果溢出
while (behind < ahead) {
curSum = data[behind] + data[ahead];
if (curSum == sum) {
result.add(data[behind]);
result.add(data[ahead]);
break;
} else if (curSum < sum) {
behind++;
} else {
ahead--;
}
}
return result;
}
LeetCode
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res =new int[2];
if(nums == null || nums.length == 0){
return res;
}
int start = 0;
int end = nums.length-1;
while (start < end){
if((nums[start] + nums[end]) > target){
--end;
}else if((nums[start] + nums[end]) < target){
++start;
}else {
System.out.println(start +" "+ end + " "+nums[start] + " "+nums[end]);
res[0] = start+1;
res[1] = end+1;
return res;
}
}
return res;
}
}
题目二：输入一个正数s，打印出所有和为s 的连续正数序列（至少两个数）
问题
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
思路
设定两个指针，一个指向第一个数，一个指向最后一个数，在此之前需要设定第一个数和最后一个数的值，由于是正数序列，所以可以把第一个数设为1，最后一个数为2（因为是要求是连续正数序列，最后不可能和第一个数重合）。下一步就是不断改变第一个数和最后一个数的值，如果从第一个数到最后一个数的和刚好是要求的和，那么把所有的数都添加到一个序列中；如果大于要求的和，则说明从第一个数到最后一个数之间的范围太大，因此减小范围，需要把第一个数的值加1，同时把当前和减去原来的第一个数的值；如果小于要求的和，说明范围太小，因此把最后一个数加1，同时把当前的和加上改变之后的最后一个数的值。这样，不断修改第一个数和最后一个数的值，就能确定所有连续正数序列的和等于S的序列了。
注意：初中的求和公式应该记得吧，首项加尾项的和乘以个数除以2，即sum = (a + b) * n / 2。
ublic class Test1 {
public static void main(String[] args) {
System.out.println(FindContinuousSequence(15));
}
/*
*初始化small=1，big=2;
*small到big序列和小于sum，big++;大于sum，small++;
*当small增加到(1+sum)/2是停止
*/
public static ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>();
if(sum < 3) {
//不重复，最少有两个数字
return res;
}
int small = 1;
int big = 2;
//因为是两个数，假设small是这个
//，big假设也是这个，和为sum+1，所以到此就可以停了，后面肯定更大
while(small !=(sum+1)/2) {
int cursum = SumOfList(small, big);
if(cursum == sum) {
for (int i = small; i <= big; i++) {
list.add(i);
}
res.add(new ArrayList<>(list));
list.clear();
//清理掉
big++;
//找到一组，继续big++，找下一组满足要求的。
}
else if (cursum > sum) {
small++;
}
else {
big++;
}
}
return res;
}
//计算list内的数据的和
public static int SumOfList(int small, int big) {
int sum = 0;
for (int i = small; i <= big; i++) {
sum +=i;
}
return sum;
}
}
LeetCode
这个地方与剑指offer不一样的地方是没有至少为2.
给定一个正整数 N，试求有多少组连续正整数满足所有数字之和为 N?
示例 1:
输入: 5
输出: 2
解释: 5 = 5 = 2 + 3，共有两组连续整数([5],[2,3])求和后为 5。
示例 2:
输入: 9
输出: 3
解释: 9 = 9 = 4 + 5 = 2 + 3 + 4
示例 3:
输入: 15
输出: 4
解释: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
说明: 1 <= N <= 10 ^ 9
大神代码
public static int consecutiveNumbersSum(int N) {
// 2N = k(2x + k + 1)
int ans = 0;
for (int k = 1; k <= 2*N; ++k) {
if (2 * N % k == 0) {
int y = 2 * N / k - k - 1;
if (y % 2 == 0 && y >= 0)
{
//System.out.print(y / 2 + " "+"k为"+k);
for(int i =1;i <= k;i++){
System.out.print((y / 2 + i)+" "+ " ");
}
System.out.println();
ans++;
}
}
}
return ans;
}- 时间复杂度：O(N)O(N)。
- 空间复杂度：O(1)O(1)。
代码2
class Solution {
public int consecutiveNumbersSum(int N) {
while ((N & 1) == 0) N >>= 1;
int ans = 1, d = 3;
while (d * d <= N) {
int e = 0;
while (N % d == 0) {
N /= d;
e++;
}
ans *= e + 1;
d += 2;
}
if (N > 1) ans <<= 1;
return ans;
}
}
京公网安备 11010502036488号