题目一:和为s的两个数字。
输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,则输出任意一对即可。
练习地址
https://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b
参考答案
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
ArrayList<Integer> result = new ArrayList<>();
if (array == null || array.length < 2) {
return result;
}
int start = 0, end = array.length - 1;
while (start < end) {
int s = array[start] + array[end];
if (s == sum) {
result.add(array[start]);
result.add(array[end]);
return result;
} else if (s < sum) {
start++;
} else {
end--;
}
}
return result;
}
}
复杂度分析
- 时间复杂度:O(n)。
- 空间复杂度:O(1)。
题目二:和为s的连续正数序列。
输入一个正数s,打印出所有和为s的连续正数序列(至少包含两个数)。例如,输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以打印出3个连续序列1 ~ 5、4 ~ 6和7 ~ 8。
练习地址
https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe
参考答案
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (sum < 3) {
return result;
}
int start = 1, end = 2, mid = (sum + 1) / 2, s = start + end;
while (end <= mid) {
if (s == sum) {
ArrayList<Integer> list = new ArrayList<>();
for (int i = start; i <= end; i++) {
list.add(i);
}
result.add(list);
end++;
s += end;
} else if (s < sum) {
end++;
s += end;
} else {
s -= start;
start++;
}
}
return result;
}
}
复杂度分析
- 时间复杂度:O(n)。
- 空间复杂度:O(1)。
网友评论