加法序列算法

Question

我正在练习面试的算法,并且在职业杯和SO上遇到了这个问题. 一个附加序列号是在分成两个不同数字形式的添加剂序列号时.

Ex: 1235 (split it 1,2,3,5) Ex: 12122436(split 12,12,24,36) 给定范围找到所有加性序列号？

以下是我尝试过的,我知道它效率不高,不确定它的复杂程度.此外,它没有找到像我感兴趣的53811和12122436这样的数字.如果有人可以指导我正确的方向或提出更简单有效的方法,我将非常感激.谢谢!

#include <stdio.h>

void check_two_num_sum(int,int);
void check_sum(int);
int flag = 0;

int main(){

int high,low;
printf("Enter higher range\n");
scanf("%d",&high);
printf("Enter lower range\n");
scanf("%d",&low);
check_two_num_sum(high,low);

return 0;
}

void check_two_num_sum(int high, int low)
{
  flag=0;
  for(low;low<high;low++)
  {
    check_sum(low);  
    if(flag==1)
    {
       printf("this value has additive sequence %d \n",low);
       flag = 0; 
     }
  }
}

void check_sum(int input)
{
   int count = 1;
   int capture, result, temp_res=0, n=0;

   if(n==0){
    result = input%10;
        n++;
        input = input/10;
        capture = input;
    }

   while(input!=0)
   {
     temp_res = temp_res + input%10;    

     if(count ==2)
      {
         if(result == temp_res)
          { 
         if(capture < 100)
        {       flag = 1;
                    break; 
        }

         else{
              check_sum(capture);
        }
           }

          else {
          break;
        }
        } 
    count++;
    input = input/10;
  }
}

Answer 1

假设原始序列的长度为n。一个明显可行的方法是强制枚举第一个和第二个元素的长度，并检查它在线性时间内是否正确。这种方法需要O(n ^ 3)时间。

您声称您的方法需要O(n)时间，但从您的实现来看，我怀疑您是否n表示原始序列的长度。