57.和为s的数字（简单）

考点：本题考查知识迁移能力

题目一描述：和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

思路：双指针

第一个指针指向数组的第一个数字（最小的），第二个指针指向数组的最后一个数字（最大的），不断移动指针，找到这两个数。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        if(nums == null || nums.length<=0)
            return result;
        int left = 0;
        int right = nums.length-1;
        while(right>left){
            int sum = nums[left] + nums[right];
            if(sum==target){
                result[0] = nums[left];
                result[1] = nums[right];
                return result;
            }
            else if(sum>target)
                right--;
            else
                left++;
        }
     return result;         
    }
}

代码中只有一个while循环从两端向中间扫描数组，时间复杂度为O(n)

题目二描述：和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 ：
输入：target = 9
输出：[[2,3,4],[4,5]]

思路一：数学公式

利用等差数列公式Sn=n(a1+an)/2

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer> > result = new ArrayList<ArrayList<Integer>>();
        for(int i=1;i<=(sum-1)/2;i++){
            for(int j=i+1;j<=sum-1;j++){
                //等差数列公式
                if((i+j)*(j-i+1)==2*sum){
                    ArrayList<Integer> newArray = new ArrayList<Integer>();
                    for(int k=i;k<=j;k++){
                         newArray.add(k);
                    }
                    result.add(newArray);
                }
            }
        }
       return result;
    }
}

思路二：双指针

不断移动指针逼近结果值

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        int small = 1;
        int big = 2;
        while(big > small){
            int cur = (big + small) * (big - small + 1)/2;
            if (cur == sum){
                ArrayList<Integer> list = new ArrayList<>();
                for (int i = small; i <= big; i++){
                    list.add(i);
                }
                result.add(list);
                small++;
            }else if (cur < sum ){
                big++;
            }else 
                small++;
        }
        return  result;
    }
}