Java Map Solution in O(n)

    public List<Integer> twoSum(int[] arr, int k){
        if(arr.length < 2)
            return new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i<arr.length; i++){
            if(!map.containsKey(arr[i])){
                map.put(k - arr[i], i);
            } else {
                return new ArrayList<>(){{
                    add(map.get(arr[i]), i);
                }}
            }
        }
    }