AlgoPressAppearance
57-II-和为s的连续正数序列
题目描述
https://leetcode.cn/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
思路
因为必须两个数，所以结尾条件为 <= target + 1 /2 连续的序列和，可以用当前的所有累计和 减去 前缀和，结果等于 target 即满足条件 使用Hash表缓存前缀和，则可以加速找到对应的索引
csharp
public class Solution {
List<IList<int>> result = new List<IList<int>>();
private void AddRange(int start, int end){
List<int> list = new List<int>();
for(int i=start;i<=end;i++){
list.Add(i);
}
result.Add(list);
}
public int[][] FindContinuousSequence(int target) {
Dictionary<int,int> dict = new Dictionary<int,int>();
int sum = 0;
int end = (target + 1) / 2;
for(int i=1; i<=end; i++){
sum+=i;
dict.Add(sum,i);
if(sum == target){
AddRange(1,i);
}
else if(dict.ContainsKey(sum - target)){
int key = sum-target;
AddRange(dict[key]+1,i);
}
}
int[][] arr = new int[result.Count][];
for(int i=0;i<result.Count; i++){
arr[i] = result[i].ToArray();
}
return arr;
}
}