🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 1099. Two Sum Less Than K
Сложность: easy
Дан массив целых чисел nums и целое число k. Верните максимальную сумму, такую что существуют i < j, при которых nums[i] + nums[j] = sum и sum < k. Если не существует таких i и j, удовлетворяющих этому условию, верните -1.
Пример:
Input: nums = [34,23,1,24,75,33,54,8], k = 60
Output: 58
Explanation: We can use 34 and 24 to sum 58 which is less than 60.
👨💻 Алгоритм:
1⃣Отсортируйте массив.
2⃣Установите указатели: левый на начало массива, правый на конец.
3⃣Пока левый указатель меньше правого:
Если сумма элементов по указателям меньше k, обновите максимальную сумму и сдвиньте левый указатель вправо.
Иначе сдвиньте правый указатель влево.
Верните максимальную сумму.
😎 Решение:
public class Solution {
public int TwoSumLessThanK(int[] nums, int k) {
int answer = -1;
int[] count = new int[1001];
foreach (int num in nums) {
count[num]++;
}
int lo = 1, hi = 1000;
while (lo = k || count[hi] == 0) {
hi--;
} else {
if (count[lo] > (lo < hi ? 0 : 1)) {
answer = Math.Max(answer, lo + hi);
}
lo++;
}
}
return answer;
}
}
Ставь 👍 и забирай 📚 Базу знаний
