剑指Offer 41 和为s的两个数字vs和为s的连续正整数列

和为s的两个数字

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

思路

暴力法不说了

头尾指针挨个扫呗，具体的想法是这样的，一个指针放在最后最大的值哪里，一个指针放在最前面最小的值哪里；如果此时小的话，你肯定不能移动尾指针吧，你就移动头指针；（1，2，3）找到和为5 开始是这样的（1，2，3），可是这个小啊，移动指针（1，2，3）；基本就是这样，那如果大的话，就是移动尾指针了，向前移动

代码

static   public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
            int head = 0 ;
            int end = array.length-1;
            ArrayList<Integer> arrayList = new ArrayList<>();
            if (array==null||array.length==0)
                return arrayList;
                     while (head<end)
            {
                if (array[head]+array[end]>sum)             //大于情况，向前移动尾指针
                    end--;
                else if (array[head]+array[end]<sum)        //小于情况，向后移动头指针
                    head++;
                if (array[head]+array[end]==sum)
                {
                    arrayList.add(array[head]);
                    arrayList.add(array[end]);
                    break;
                }
            }
            return arrayList;
    }

和为s的连续正整数列

题目描述

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

思路

和第一种一样，只不过此时要携带头指针和尾指针之间的和；所以头指针和尾指针起始值就是1，2；这样扫描过去；尾指针扫过去加入sum，头指针移动，删除；这样就找到了；
通过求和公式（(a1+an)*n/2=s），
将(an+a1)=k ，(an-a1+1)=l；这样就获得了k，l关于a1，an的方程
an=(k+l-1)/2 a1=(k-l+1)/2，然后不管你是循环还是枚举，总会得出结果的；

代码

ArrayList<ArrayList<Integer> > arrayLists = new ArrayList<>();
 static   public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
     if (sum<3)
         return arrayLists;
     int small= 1;
     int big = 2;
     int middle = (sum+1)>>1;
     int curSum = small+big;
     while (small<middle)
     {
         if (curSum==sum)
             Print(small,big);
         while (curSum>sum&&small<middle)  //默认就应该是big++，因为其实位置是1,2；
         {
             curSum-=small;
             small++;
             if (curSum==sum)
                 Print(small,big);
         }
         big++;
         curSum+=big;
     }
     return  arrayLists;
   }

public ArrayList<ArrayList<Integer> > FindContinuousSequence1(int sum) {
      //int middle = sum>>1;
      /*
      (an+a1) -->k
      (an-a1+1) -->n
      k*n = 2*sum
      所以k和n一定不能同时大于2*sum的开方；当a是整数范围，k，n一定不能相等
       */
      int middle = (int)Math.sqrt(2*sum);  //
      for ( int n = middle;n>=2;n--)
      {
          if ((2*sum%n)==0)
          {
              int k = sum*2/n;              //n*k = sum*2
              if ((k^n)%2==1)               //一个是奇数，一个是偶数
              {
                  int a1 = (k-n+1)/2;
                  int an = (k+n-1)/2;
                  ArrayList<Integer> arrayList= new ArrayList<>();
                  for (int i = a1; i <= an; i++) {
                      arrayList.add(i);
                  }
                  arrayLists.add(arrayList);
              }
          }
      }
      return  arrayLists;
    }

收获

好几天没编程了，赶紧找回状态吧；
学以致用啊，自己用了个异或运算，感觉超牛；
好好学数学啊！

2017-04-05