2021-02-10 剑指 Offer 57 - II. 和为s

题目地址

https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/

题目描述

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
 
限制：
1 <= target <= 10^5

思路

1. 暴力解法，从1开始，往后递增，看和是否可以等于目标值，如果可以就记录这个序列。
   一个优化的点是如果和已经大于目标值就没必要往后递增了。和j <= target/2 + 1作用类似，提前结束循环。

题解

/**
 * @Author: vividzcs
 * @Date: 2021/2/10 10:03 下午
 */
public class FindContinuousSequence {
    public static void main(String[] args) {
        int target = 9;
        int[][] result = findContinuousSequence(target);

        result = findContinuousSequenceV2(target);

        for (int i=0; i<result.length; i++) {
            for (int j=0; j<result[i].length; j++) {
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static int[][] findContinuousSequenceV2(int target) {
        List<int[]> result = new ArrayList<>();
        if (target <= 1) {
            int[] arr = new int[1];
            arr[0] = target;
            result.add(arr);
            return convertToArrayV2(result);
        }
        for (int i=1; i< target; i++) {
            int sum = 0;
            for (int j=i; j<target; j++) {
                sum += j;
                if (sum == target) {
                    int[] arr = new int[j - i + 1];
                    for (int index=0,value=i; value<=j; index++,value++) {
                        arr[index] = value;
                    }
                    result.add(arr);
                    break;
                }
                if (sum > target) {
                    break;
                }
            }
        }
        return convertToArrayV2(result);
    }

    private static int[][] convertToArrayV2(List<int[]> result) {
        int[][] arr = new int[result.size()][];
        for (int i=0; i<result.size(); i++) {
            arr[i] = result.get(i);
        }
        return arr;
    }

    private static int[][] findContinuousSequence(int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (target <= 1) {
            List<Integer> list = new ArrayList<>();
            list.add(target);
            result.add(list);
            return convertToArray(result);
        }
        for (int i=1; i< target; i++) {
            int sum = 0;
            List<Integer> list = new ArrayList<>();
            for (int j=i; j<target; j++) {
                sum += j;
                list.add(j);
                if (sum == target) {
                    result.add(list);
                    break;
                }
                if (sum > target) {
                    break;
                }
            }
        }
        return convertToArray(result);
    }

    private static int[][] convertToArray(List<List<Integer>> result) {
        int[][] arr = new int[result.size()][];
        for (int i=0; i<result.size(); i++) {
            arr[i] = new int[result.get(i).size()];
            for (int j=0; j<result.get(i).size(); j++) {
                arr[i][j] = result.get(i).get(j);
            }
        }
        return arr;
    }
}