《C语言入门100例》(第2例) 给定 n，求 1 + 2 + 3 + ... + n 的和给定 n，求 1 + 2 + 3 + ... + n 的和

【第02题】给定 n，求 1 + 2 + 3 + … + n 的和 | 四种解法

• • 主要知识点
  • 习题
  • • 1. 剑指 Offer 64. 求1+2+…+n
    • • 题目描述
      • 初见
      • 思路
      • 代码
    • 2. Sum Problem
    • • 题目描述
      • 初见
    • 3. 剑指 Offer 57 - II. 和为s的连续正数序列
    • • 题目描述
      • 初见
      • 思路
      • 代码
  • 总结

计算时注意数值计算在计算机内的溢出。与理论计算不同，算法设计中要时刻注意数值计算溢出的情况，以计算 n ∗ ( n + 1 ) / 2 n * (n + 1) / 2 n∗(n+1)/2 为例，通常有以下 3 种解决方法：

1. 通过循环规避可能溢出的计算，将上式中的乘法通过循环降级为加法，规避 n ∗ ( n + 1 ) n * (n + 1) n∗(n+1) 可能产生的溢出;
2. 通过改变计算顺序先规避可能的溢出，如先算一步除法再算乘法;
3. 通过提升变量类型扩大内存规避溢出，如将 n n n 从 int 扩展为 unsigned int 或 long long

计算机的数值计算在工程运用中是一个更加复杂的问题，不止需要考虑计算时变量类型导致的溢出，更需要考虑数值稳定性（尤其是迭代计算中的稳定性）。

求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
限制：1 <= n <= 10000

那么为什么不能用 n × ( n + 1 ) / 2 n times (n + 1) / 2 n×(n+1)/2 呢？
初见败北。

在上述条件限定下，编程中常用的运算符只剩下了加减法，位运算符，以及逻辑运算符。对于数列求和，常用的有两种方法：循环求和与公式计算。

1. 从循环求和角度出发，要找到一种代替 if else 语句的写法，恰好逻辑运算符可以满足这一要求。由于逻辑运算符的短路特性，对于以下 if 语句：

   if (condA) {
       do A;
   } else {
   	do B;
   }
   

   其效果等价于：

   (condA) && (do A); // condA == true, 才执行 do A
   (!condA) && (do B); // condA == false, 才执行 do B
   

2. 从公式计算的角度出发，我们可以用 x >> 1 完成 x / 2 x / 2 x/2 的计算，但是要找到一种代替乘法的方法。回顾一下这里，就会发现…只需要使用逻辑运算符，就可以替换原有的 if else 语句，将乘法以如下形式完成：

   int multiply(int A, int B) {
        int result(0);
        for (int i = 0; i < 32; ++i) {
            // 若 B 为奇数，则 result = result + A（通过 && 实现奇数条件进入）
            (B & 0x1) && (result += A);
            // 已解决 B 为奇数的情况，此时 B 为偶数
            A = (unsigned int)A << 1;
            B = B >> 1;
        }
        return result;
    }
   

   至于 for 循环…那么官方的说法是：不过 14 次而已（ 1 ≤ n ≤ 10000 1 leq n leq 10000 1≤n≤10000），写就完事儿了！

解法1：使用逻辑运算符代替 if else

int sumNums(int n) {
    n > 0 && (n += sumNums(n - 1));
    return n;
}

解法2：使用逻辑运算符代替 if else，使用位运算与加法代替乘法

int sumNums(int n) {
    int ans = 0, A = n, B = n + 1;

    (B & 1) && (ans += A);
    A <<= 1;
    B >>= 1;

    // 再来 13 个

    return ans >> 1;
}

输入一串 n，对每个输入的 n 求相对应的 1+2+…+n 的值并按格式输出

网站提交没上去，看着难点在于输入输出。总之，鸽了 

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
限制：1 <= target <= 10^5

连续正整数序列，别问，问就是直接搜索：

vector> findContinuousSequence(int target) {
    vector> result;
    for (int i = 1; i < target; ++i) {
        for (int j = 1; j < target; ++j) {
            int curResult = ((2 * i + j) * (j + 1) / 2);
            if (curResult == target) {
                vector curVec;
                for (int k = i; k <= i + j; ++k) {
                    curVec.push_back(k);
                }
                result.push_back(curVec);
            } else if (curResult > target) {
                break;
            }
        }
    }
    return result;
}

1. 数学方法
   为了提高效率，我们进行一点点计算，对于连续整数，令和为 t a r g e t target target 的公式如下：
   [ i + ( i + j ) ] × ( j + 1 ) / 2 = t a r g e t j 2 + ( 2 i + 1 ) j + 2 i − 2 t a r g e t = 0 ; [i + (i + j)] times (j + 1) / 2 = target \ j^2 + (2i + 1)j + 2i - 2target = 0; [i+(i+j)]×(j+1)/2=targetj2+(2i+1)j+2i−2target=0;
   其中， i i i 为当前搜索的起始数字， j j j 为向后搜索数的个数。对于上述 j j j 二元一次方程，求 Δ Delta Δ，若 Δ < 0 Delta < 0 Δ<0 则无解; 若 Δ > = 0 Delta >= 0 Δ>=0，则看 Δ Delta Δ 是否为完全平方数，若不是则舍弃，若是则右侧根为 j j j 的解（左侧不满足条件）

2. 双指针
   不用任何计算，仅使用双指针竟然就能达到 O ( n ) O(n) O(n) 效率！心动了！！
   我们用两个指针 l l l 和 r r r 表示当前枚举区间 [ l , r ] [l, r] [l,r]，可计算出区间和 s u m sum sum，共有三种情况：

   1. s u m < t a r g e t sum < target sum
   2. s u m = = t a r g e t sum == target sum==target，当前结果符合，搜索下一区间，指针 l l l 应当向右扩展，即 l + = 1 l += 1 l+=1
   3. s u m > t a r g e t sum > target sum>target，当前结果偏大，指针 l l l 应当向右扩展，即 l + = 1 l += 1 l+=1

   此方法其实是对直接搜索的优化，因为直接搜索没有考虑区间与区间的信息复用，只是单纯的枚举起点，然后累加；而该方法考虑到了如果已知 [ l , r ] [l,r] [l,r] 的区间和等于 t a r g e t target target ，那么枚举下一个起点的时候，区间 [ l + 1 , r ] [l+1,r] [l+1,r] 的和必然小于 t a r g e t target target ，我们就不需要再从 l + 1 l+1 l+1 开始重复枚举，而是从 r + 1 r+1 r+1 开始枚举，充分利用已知信息来优化时间复杂度。

解法1：数学方法

vector> findContinuousSequence(int target) {
    vector> result;
    for (int i = 1; i < target / 2 + 1; ++i) {
        int a = 2 * i;
        // 使用 long long 避免计算溢出
        long long delta = (long long)(a + 1)*(a + 1) - 4*(a - 2*target);
        if (delta < 0) {
            continue;
        } else {
            int j = ((-a - 1) + sqrt(delta)) / 2;
            // delta 需为完全平方数，此处直接验证一次结果
            if ((a + j) * (j + 1) / 2 == target) {
                vector curVec;
                for (int k = 0; k < j + 1; ++k) {
                    curVec.push_back(i + k);
                }
                result.push_back(curVec);
            }
        }
    }
    return result;
}

解法2：双指针

vector> findContinuousSequence(int target) {
    vector> result;
    for (int i = 1, j = 2; i < target / 2 + 1;) {
        int secResult = (i + j) * (j - i + 1) / 2;
        if (secResult < target) {
            // 扩大搜索区间
            j++;
        } else if (secResult == target) {
            // 存入结果并搜索 [i + 1, j + 1]
            vector curVec;
            for (int k = i; k <= j; ++k) {
                curVec.push_back(k);
            }
            result.push_back(curVec);
            i++;
            j++;
        } else if (secResult > target) {
            // 缩小搜索区间
            i++;
        }
    }
    return result;
}

1. 数值计算与理论计算的区别
2. 可以使用逻辑运算符代替 if()...else()... 语句
3. 使用位运算与加法完成乘法运算
4. 双指针减少区间搜索量