I want to use bitset in C++. So the time complexity is O(n). However, I failed to include<bitset>. The compile error is "Line 7: 'bitset' was not declared in this scope".
So, are there any other way to solve this problem and the complexity is O(n);
@likunjk, Could you share your code, algorithm and the reason you think the test case is weak in a new question? I am curious of it. Thanks.
@Shangrila, Because I find the O(n) algorithm just use map record the index of numbers[i].
But in these case vector{3,2,4} target=6. when I linear scan the vector in index i = 0;
int k = target - numbers[0], so now I need another 3, look up the map I find map[3] = 0.
Ok, Now I will think I find the answer{0,0}. just simple translate become {1,1}.
Actually, the true answer is {2,3}.
@Shangrila, Actually, we can solve this problem, Just judge whether two index equal.
That's to say, There still exists O(n) algorithm.
@likunjk, I think you just think in this way, but for such situation could do more extra check to avoid it. As problem has clarified that there is only 1 solution for each input, I believe using map can do solve it.
@Shangrila, there exists only one solution. My test case meet it.
This is a solution report I found, I test it use my case, I get wrong answer. I just wan to say, leetcode test cases not cover all cases.
http://blog.csdn.net/doc_sgl/article/details/12115067
@likunjk, thank you very much! This is a good catch. Appreciate your sharing. Hope 1337 will soon add such test case to avoid this WA solution could pass the OJ.
@likunjk Thanks very much for pointing that out. Additional test cases are added to this problem.