这个问题如果直接使⽤ for 循环超级简单重拳出击时间复杂度为 O(n) 。代码如下javapublic class Solution { public int Sum_Solution(int n) { int sum 0; for (int i 1; i n; i) { sum i; } return sum; } }可是上⾯的明显违反了使⽤for 循环的原则乘除法试试公式法 123...(n-1)n n * (n1)/2 ,javapublic class Solution { public int Sum_Solution(int n) { if (n 0) { return n * (n 1) / 2; } return 0; } }但是上⾯的做法同样是使⽤乘法也违反了原则那么要不使⽤循环也不适⽤乘法怎么做呢递归递归可以模拟出循环⼏乎所有的for 循环操作都可以以递归的⽅式实现。每⼀次递归我们让n 减少1 直到减少为0 。javapublic class Solution { public int Sum_Solution(int n) { if (n 0) { return n Sum_Solution(n - 1); } return 0; } }时间复杂度为O(n)空间复杂度也是O(n)位运算乘法位运算乘法法通过位运算实现乘法操作思路将n(n1)用位运算实现然后右移1位代替除以2javapublic class Solution { public int sum(int n) { // 计算n*(n1) using bit manipulation int result multiply(n, n 1); // 右移1位相当于除以2 return result 1; } /** * 位运算实现乘法利用俄罗斯农民算法 * 原理a * b (a i)的和其中i对应b中为1的位 */ private int multiply(int a, int b) { int result 0; // 当a不为0时继续循环 while (a ! 0) { // 如果a的最低位是1则加上对应的b值 if ((a 1) ! 0) { result b; } // a右移1位b左移1位 a 1; b 1; } return result; } // 无循环的位运算乘法版本符合要求 public int sumNoLoop(int n) { int res multi(n, n 1); return res 1; } private int multi(int a, int b) { int res 0; // 通过多个位判断代替循环 res ((a 1) 1) ? b : 0; a 1; b 1; res ((a 1) 1) ? b : 0; a 1; b 1; // 继续处理更多位...根据n的范围确定需要处理的位数 return res; } }时间复杂度O(log n) - 取决于数字的位数空间复杂度O(1)案例解析text计算 13 × 9: 13 1101(二进制) 9 1001(二进制) 13 × 9 13 × (1 0 0 1) 按位展开 (130) (133) 对应9中为1的位 13 104 117