Вариант 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; }