Technically, if all values in the array are the same value X, and the target is 2X, you can't do better than O(n^2), because just writing writing all valid solu

Technically, if all values in the array are the same value X, and the target is 2X, you can't do better than O(n^2), because just writing writing all valid solutions is O(n^2). If you can create a new array containing indices to the original array, sort the new array, and use two pointers starting at the beginning and the end of the sorted array to find a solution, it takes O(n×log(n)) time. It is not necessary to assume that the solution is unique, assuming it is okay to simply write one of the possible solutions. If all values are between 1 and k, and you can make a k-sized array, you can find a solution in O(n+k). No matter what you do, you can't get better than O(n). The important thing is that there is more than 99% chance you will never have to solve this problem in your job; and even in the case you would, there is 95% chance that the O(n×log(n)) solution would be acceptable regardless of whether it is the best possible or not.