Two Sum II – Input Array Is Sorted
Leetcode #167 | Medium | Два указателя
Идея
Два указателя навстречу друг другу, если sum < target двигаем левый, иначе правый, при равенстве возвращаем результат
Big-O
- Время
O(N) - Память
O(1)
Код
class Solution {
public int[] twoSum(int[] numbers, int target) {
int l = 0, r = numbers.length - 1;
while (l < r) {
int sum = numbers[l] + numbers[r];
if (sum > target) r--;
else if (sum < target) l++;
else return new int[]{l + 1, r + 1};
}
return new int[0];
}
}