剑指Offer Java版 面试题57：和为s的数字

题目一：和为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)。

👉剑指Offer Java版目录
👉剑指Offer Java版专题