例子
100=2×50(因为两个都是偶数,无法找出=100的序列。如最接近的也是50+51=101.)
100=4×25(因为25为奇数,可以分为(12,13)、(11,14)、(10,15)、(9,16),又因为需要4个25,所以这四个对刚好满足。即[9, 16]成立。)
100=5×20(因为5为奇数,因此可以从20开始,依次往前后加入(5-1)/2个数。即[18, 22]成立。)
规律:
for(i从2到sum/2){ if(sum不能被i整除) continue; a=n/i;// 即上方的50/25/20等 if(i为奇数)// 对应上方5×20 从a开始,往两边扩(i-1)/2个; else// i为偶数,对应上方1、 2情况 if(a为偶数) continue;// 对应情况1,不能是两个偶数 else 从a/2和(a/2)+1开始,向两边扩充找i个。对应情况2. } }
注意:
- 不能被2整除的特殊情况,即sum=1or2or3,单独考虑。因为如果进入下方的for,因为无法被sum/2以下的值除尽,所以找不到有效情况,但实际上3有成立情况[1,2];
- 往两边扩的时候不能扩到复数,如100不能有从负开始的情况。
代码:
vector<vector<int> > FindContinuousSequence(int sum) { int s = 0; vector<int> nums; vector<vector<int> > v_all_path; map<int, vector<int> > m_all_path; if(sum <= 2){ return v_all_path; } // 若无法被2整除,则需要加上sum/2及sum/2 + 1 if(sum % 2 == 1){ nums.push_back(sum / 2); nums.push_back(sum / 2 + 1); m_all_path[nums[0]] = nums; nums.clear(); } for(int i = 2; i <= sum / 2; i++){// 一开始选择sqrt是因为超过了会重复。但对于15来说,÷5=3的情况和÷3=5的情况不同,需要对称考虑所以改为sum/2 if(sum % i){// 无法i整除 continue; } int quotient = sum / i;// 商 if(i % 2){// 为奇数 if((quotient - ((i - 1) / 2)) <= 0){// 超过下界0的序列不考虑 continue; } nums.push_back(quotient); for(int j = 1; j <= (i - 1) / 2; j++){ nums.insert(nums.begin(), quotient - j); nums.push_back(quotient + j); } m_all_path[nums[0]] = nums; nums.clear(); } else{// 为偶数 if(!(quotient % 2))// 两个都为偶数,无法分割 continue; int begin = quotient / 2; int end = quotient / 2 + 1; if((begin - i + 1) <= 0){// 同上,超过下界0的序列不考虑 continue; } for(int j = 0; j < i; j++){// 加i组,每组的和=quotient nums.insert(nums.begin(), begin - j); nums.push_back(end + j); } m_all_path[nums[0]] = nums; nums.clear(); } } for(map<int, vector<int> >::iterator it = m_all_path.begin(); it != m_all_path.end(); it++){ v_all_path.push_back(it->second); } return v_all_path; }
分析:
T(n)=O(n/2),因为只需要判断sum/2。S(n)=O(1)(存储路径不考虑)。