剑指 Offer 57. 和为s的两个数字 & II. 和为s的连续正数序列

I题目描述：

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

解析：

二分法

Java:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        for(int i = 0; i < nums.length; i++) {
            if(nums[left] + nums[right] < target) {
                left++;
            } else if(nums[left] + nums[right] > target) {
                right--;
            } else {
                return new int[] {nums[left], nums[right]};
            }
        }
        return new int[0];
    }
}

JavaScript:

var twoSum = function(nums, target) {
    let set = new Set();
    for(let i = 0; i < nums.length; i++) {
        if(!set.has(target - nums[i])) {
            set.add(nums[i]);
        } else {
            return [nums[i], target - nums[i]];
        }
    }
    return [];
};

II题目描述：

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

解析：

数学方法

Java:

class Solution {
    public int[][] findContinuousSequence(int target) {
        int left = 1, right = 1, sum = 0, end = target / 2;
        List<int[]> res = new ArrayList<>();
        while(left <= end) {
            if(sum < target) {
                sum += right;
                right++;
            } else if(sum > target) {
                sum -= left;
                left++;
            } else {
                int[] arr = new int[right - left];
                for(int i = left; i < right; i++) {
                    arr[i - left] = i;
                }
                res.add(arr);
                sum -= left;
                left++;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

JavaScript:

var findContinuousSequence = function(target) {
    let left = 1, right = 1, sum = 0, end = target / 2;
    let res = [];
    while(left <= end) {
        if(sum < target) {
            sum += right;
            right++;
        } else if(sum > target) {
            sum -= left;
            left++;
        } else {
            let arr = [];
            for(let i = left; i < right; i++) {
                arr[i - left] = i;
            }
            res.push(arr);
            sum -= left;
            left++;
        }
    }
    return res;
};