A typical solution would be an n^2. However, the trick is to use an auxiliary data structure to gain efficiency at the cost of additional space. Since duplicates are possible, it is best to use the map as we go rather than saving everything in one pass. This is demonstrated below:

```
public int[] twoSum(int[] nums, int target) {
int[] ret = new int[] {};
if(nums.length==0) {
return ret;
}
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++) {
Integer idx = map.get(target-nums[i]);
if(idx!=null) {
return new int[] {idx,i};
}
map.put(nums[i],i);
}
return ret;
}
```