美文网首页剑指 Offer Java版
剑指Offer Java版 面试题57:和为s的数字

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

作者: 孙强Jimmy | 来源:发表于2019-08-06 10:09 被阅读1次

    题目一:和为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版专题

    相关文章

      网友评论

        本文标题:剑指Offer Java版 面试题57:和为s的数字

        本文链接:https://www.haomeiwen.com/subject/yvtidctx.html