剑指 Offer 57 - II. 和为s的连续正数序列
left
、right
,初始的时候left=left=1
left < right
sum
与target
进行比较:
target > sum
,说明窗口大了,需要将当前left
从sum
中删除,同时left
右移一步target < sum
,说明窗口笑了,需要将当前right
从sum
中删除,同时right
右移一步target = sum
,则找到一段序列等于target
,记录下该子序列,同时left
向右移动一步target=9
为例,求解流程如下:
class Solution { public int[][] findContinuousSequence(int target) { int sum = 3; int left = 1; int right = 2; List<int[]> res = new ArrayList<>(); while (left < right) { // 当前窗口符合要求 if (sum == target) { // 加入到结果集中 int[] temp = new int[right - left + 1]; for (int i = left; i <= right; i++) { temp[i-left] = i; } res.add(temp); } // 窗口过大,要缩小窗口 if (sum >= target) { // 这里要先将left从sum中减去,然后再右移一位,因为当前left是即将被移出窗口,这样才能保证left是窗口的左边界 sum -= left; left++; } else if (sum < target) { // 这里要先将right自增,然后将right加入到sum中,因为先自增才能获取到窗口后一位的元素,然后加入到窗口中,保证了right是窗口的右边界 right++; sum += right; } } return res.toArray(new int[res.size()][]); } }
N=target