关于167的时间复杂度

Question

老师，您好。
如果题目改为输出所有的整数对，时间复杂度是不是也会变化呢？

Answer 1

liuyubobobo 2022-02-27 12:36:17

会。如果输出所有整数对，需要 O(n^2) 的算法。因为在最坏的情况下，整个数组的 n * (n + 1) / 2 个整数对全部满足条件。比如数组中所有元素都是 1，target 是 2。

继续加油！：）

• 提问者 qq_森_12 #1

  那有优化的方法吗？

• liuyubobobo 回复 提问者 qq_森_12 #2

  没有。解最多有这么多，把这些解无论是存储起来，还是打印出来，复杂度就这么高。这就是为什么很多问题不会要求“所有解”。

• 提问者 qq_森_12 回复 liuyubobobo #3

  老师，比如数组[1,1,1,1]
  我上面代码截图的解是：第0个和第3个，第1个和第2个
  而你的说法应该是：
  第0个和第1个，第0个和第2个，第0个和第3个
  第1个和第2个，第1个和第3个
  第2个和第3个
  需要的解法是用双层循环去找

点开查看后面1条评论