感觉上次面试被面试官带沟里去了

题目：一个未排序的数组，打印出所有可能的两个数组合，这两个数的和是指定的K。要求打印出所有元素的index.
要求空间是O(1)，并且解法能处理duplicate element

如果不考虑空间，可以借助Map<Integer, List<Integer>>数据结构做出来。但是如果要考虑时间和空间，想了很久也没有想出好的解法。当时面试官给的提示是用两边指针的方法。

现在想来面试官很可能自己也弄错了，如果用两边指针，那肯定是先把数组排序，然后两边移动指针打印所有可能的value组合，而不是index组合。因为一旦排序了，之前的index就变了，除非用O(n)的空间对integer封装保存原来的index.

各位怎么看？这个题目看上去很普通，但是加了几个小变化后就变得很难了
- 数组有重复元素
- 打印所有可能而不是第一个可能
- 打印index而不是value
- 空间要求是O(1), 时间小于O(N*N)

我的感觉，空间O(1)应该指extra O(1)，也就是input/output本身的size并不算， 不然绝对不可能O(1)啊....
这样的话通过In-place sort和two pointer能实现O(1)的Memory
如果时间小于但不等于O(N^2)的话，two pointer的右指针可以用binary search，这样就是O(nlogn)了
一点拙见，不一定对

CL_has_a_moon 发表于 2020-7-20 05:11
我的感觉，空间O(1)应该指extra O(1)，也就是input/output本身的size并不算， 不然绝对不可能O(1)啊....
...

sort完之后怎么保留index呢？题目要求要保留原index。。不用额外空间的话几乎是做不到的吧。。

lynellea 发表于 2020-7-17 03:37
直接暴力枚举？毕竟强调有空间限制，那时间复杂度该牺牲一点就牺牲一点呗，世间安有两全法。

暴力枚举也有个问题，这样去重的话怎么做到O(1)呢？如果去重没法O(1)，那复杂度是压缩不到O(n^2)的

看上去不大可能啊。。。N 的大小有限制吗？如果小于USHRT_MAX,还有可能。。。

直接暴力枚举？毕竟强调有空间限制，那时间复杂度该牺牲一点就牺牲一点呗，世间安有两全法。

lynellea 发表于 2020-07-16 12:37:38
直接暴力枚举？毕竟强调有空间限制，那时间复杂度该牺牲一点就牺牲一点呗，世间安有两全法。

楼主又说时间小于O（N^2)，肯定要sort了，但存哪

感覺他是挖坑給你跳，但是要看你怎麼跳出來...

Dustinlo 发表于 2020-7-18 08:20
感覺他是挖坑給你跳，但是要看你怎麼跳出來...

还有这种面试方式啊？太不友好了

distantstar 发表于 2020-07-17 09:14:34
楼主又说时间小于O（N^2)，肯定要sort了，但存哪

要不然 把(index, val) 用 index+val*N 代替 然后再sort？这个本质上和sort （val, index）pair 是一样的

可能的麻烦是如果N巨大就overflow了