Вариант 1: дубликаты запрещены

Получив массив целых чисел, верните индексы двух чисел так, чтобы они в сумме давали определенную цель.

Вы можете предположить, что каждый вход будет иметь ровно одно решение, и вы не можете использовать один и тот же элемент дважды.

Пример:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Решение: 1. Перебрать каждое значение в nums.
2. Найти дополнение=target-nums[i] для каждого nums[i].
3.Проверить, если уже есть на карте, вернуть новый int[] {map.get(дополнение),i};
4.else map.put(числа[i],i)

Сложность времени и пространства: O(n)

Вариант 2. Входной массив отсортирован
Решение.

public int[] twoSum(int[] numbers, int target) {
    int len = numbers.length, lo = 0, hi = len- 1;
    while (lo < hi) {
        int sum = numbers[lo] + numbers[hi];
        
        if (sum > target)       hi--;
        else if (sum < target)  lo++;
        else return new int[] {lo + 1, hi + 1};
    }
    throw new IllegalArgumentException("No solution");
}

Вариант 3.Разработайте и реализуйте класс TwoSum. Он должен поддерживать следующие операции: добавить и найти.
добавить — добавить число во внутреннюю структуру данных.
найти — найти, существует ли какая-либо пара чисел, сумма которых равна значению.
Например,
add(1); добавить (3); add(5);
find(4) -> true
find(7) -> false

Решение:

public class TwoSum {
    private Map<Integer, Integer> map = new HashMap<>();
    
    public void add(int number) {
        int count = map.containsKey(number) ? map.get(number) : 0;
        map.put(number, count + 1);
    }

    public boolean find(int value) {
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int num = entry.getKey();
            int y = value - num;
            if (y == num) {
                if (entry.getValue() >= 2)  return true;
            }
            else if (map.containsKey(y))
                return true;
        }
        return false;
    }
}

Вариант 4: содержит дубликаты
По заданному несортированному массиву целых чисел найдите все пары, которые в сумме дают определенное целевое число . Массив может содержать повторяющиеся элементы.
Вывод не должен содержать повторяющихся пар, и каждая пара должна быть в порядке возрастания, например, [1, 2] вместо [2, 1] .

public List<List<Integer>> twoSum(int[] num, int target) {
    List<List<Integer>> listSet = new ArrayList<List<Integer>>();
    Map<Integer, Integer> map = new HashMap<>();
    if (num.length < 2)  return listSet;
    for (int i = 0; i < num.length; i++) {
        int key1 = num[i], key2 = target - num[i];
        if (map.containsKey(key2) && map.get(key2) > 0) {
            List<Integer> list = new ArrayList<Integer>();
            if (key1 < key2) list = Arrays.asList(key1, key2);
            else list = Arrays.asList(key2, key1);
            
            if (!listSet.contains(list)) listSet.add(list);
            map.put(key2, map.get(key2) - 1);
        } else {
            if (!map.containsKey(key1)) map.put(key1, 1);
            else  map.put(key1, map.get(key1) + 1);
        }
    }
    return listSet;
}