手机网站 跳转,长沙公共资源交易中心官网,网站策划案例,安全优化大师下载Problem: LCR 180. 文件组合 文章目录 题目描述思路及解法复杂度Code 题目描述 思路及解法
本题目可以利用滑动窗口的技巧#xff08;滑动窗口就是双指针的运用#xff09;解决#xff0c;具体实现如下 1.逻辑上生成窗口#xff1a;让两个指针i#xff0c;j分别初始化为1… Problem: LCR 180. 文件组合 文章目录 题目描述思路及解法复杂度Code 题目描述 思路及解法
本题目可以利用滑动窗口的技巧滑动窗口就是双指针的运用解决具体实现如下 1.逻辑上生成窗口让两个指针ij分别初始化为12并定义一个用于维护“窗口”的目标整形值sum初始化为3 2.维护窗口 若sum等于target则将j-i1“窗口”内的值添加到结果集合中然后sum - iijsum j维护新的“窗口” 若sum大于target则sum - ii 若sum小于target则j sum j 复杂度
时间复杂度: O ( n ) O(n) O(n);其中 n n n为小于或等于 t a r g e t target target的数 空间复杂度: O ( n 2 ) O(n^2) O(n2) Code
class Solution {
public:/*** Two pointer* param target Target number* return vectorvectorint*/vectorvectorint fileCombination(int target) {vectorvectorint result;int i 1;int j 2;int sum 3;while (i j) {if (sum target) {vectorint temp(j - i 1);for (int k i; k j; k) {temp[k - i] k;}result.push_back(temp);sum - i;i;j;sum j;} else if (sum target) {j;sum j;} else {sum - i;i;}}vectorvectorint resultArr(result.size());for (int k 0; k result.size(); k) {resultArr[k].resize(result[k].size());for (int l 0; l result[k].size(); l) {resultArr[k][l] result[k][l];}}return resultArr;}
};
