Java | LeetCode
Задача: 259. 3Sum Smaller
Сложность: medium
Дан массив из n целых чисел nums и целое число target. Найдите количество троек индексов i, j, k, удовлетворяющих условию 0 <= i < j < k < n и nums[i] + nums[j] + nums[k] < target.
Пример:
Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]
👨💻 Алгоритм:
1⃣Отсортируйте массив nums.
2⃣Для каждого элемента nums[i] от 0 до n-3 найдите количество пар индексов j и k (где i < j < k), таких что nums[i] + nums[j] + nums[k] < target. Используйте функцию twoSumSmaller, которая ищет количество пар с суммой меньше заданного значения.
3⃣В функции twoSumSmaller используйте бинарный поиск для поиска верхней границы индекса k и подсчета количества подходящих пар.
😎 Решение:
import java.util.Arrays;
class Solution {
public int threeSumSmaller(int[] nums, int target) {
Arrays.sort(nums);
int sum = 0;
for (int i = 0; i < nums.length - 2; i++) {
sum += twoSumSmaller(nums, i + 1, target - nums[i]);
}
return sum;
}
private int twoSumSmaller(int[] nums, int startIndex, int target) {
int sum = 0;
for (int i = startIndex; i < nums.length - 1; i++) {
int j = binarySearch(nums, i, target - nums[i]);
sum += j - i;
}
return sum;
}
private int binarySearch(int[] nums, int startIndex, int target) {
int left = startIndex;
int right = nums.length - 1;
while (left < right) {
int mid = (left + right + 1) / 2;
if (nums[mid] < target) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 302 ·