Две суммы II — входной массив отсортирован
ТРИ СУММ
Контейнер с наибольшим количеством воды
Сбор дождевой воды
Лучшее время для покупки и продажи акций
Two Sum II — входной массив отсортирован — TWO POINTER
Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
const twoSum = (numbers, target) => {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
let sum = numbers[left] + numbers[right];
if (sum === target) {
return [left + 1, right + 1];
} else if (sum < target) {
left++;
} else {
right--;
}
}
};
ТРИ СУММЫ (с использованием СОРТИРОВКИ или ХЕШИРОВАНИЯ)
Input: arr[] = {0, -1, 2, -3, 1}
Output: (0 -1 1), (2 -3 1)
Explanation: The triplets with zero sum are 0 + -1 + 1 = 0 and 2 + -3 + 1 = 0
Input: arr[] = {1, -2, 1, 0, 5}
Output: 1 -2 1
Explanation: The triplets with zero sum is 1 + -2 + 1 = 0
Найдите все триплеты с нулевой суммой, используя сортировку
Временная сложность: O(n2). Требуется только два вложенных цикла, поэтому временная сложность составляет O(n2).
Вспомогательное пространство: O(1) , дополнительное пространство не требуется, поэтому сложность пространства постоянна.
Для реализации идеи выполните следующие шаги:
- Отсортируйте массив в порядке возрастания.
- Пройдите массив от начала до конца.
- Для каждого индекса i создайте две переменные l = i + 1 и r = n — 1.
- Запускать цикл до тех пор, пока l не станет меньше r, если сумма array[i], array[l] и array[r] равно нулю, затем напечатайте триплет и разорвите цикл
- Если сумма меньше нуля, увеличьте значение l. При увеличении значения l сумма будет увеличиваться по мере сортировки массива, поэтому array[l+1] › array [l]
- Если сумма больше нуля, уменьшите значение r. При уменьшении значения r сумма будет уменьшаться по мере сортировки массива, поэтому массив[r-1] ‹ массив [r].
function findTriplets(arr, n)
{
let found = false;
// sort array elements
arr.sort((a, b) => a - b);
for (let i=0; i<n-1; i++)
{
// initialize left and right
let l = i + 1;
let r = n - 1;
let x = arr[i];
while (l < r)
{
if (x + arr[l] + arr[r] == 0)
{
// print elements if it's sum is zero
document.write(x + " ");
document.write(arr[l]+ " ");
document.write(arr[r]+ " " + "<br>");
l++;
r--;
found = true;
}
// If sum of three elements is less
// than zero then increment in left
else if (x + arr[l] + arr[r] < 0)
l++;
// if sum is greater than zero then
// decrement in right side
else
r--;
}
}
if (found == false)
document.write(" No Triplet Found" + "<br>");
}
Найдите все триплеты с нулевой суммой, используя хеширование (SET)
Временная сложность: O(n2), поскольку требуются два вложенных цикла, поэтому временная сложность составляет O(n2).
Вспомогательное пространство: O(n) , Поскольку требуется HashSet, сложность пространства является линейной.
Для реализации идеи выполните следующие шаги:
- Создайте HashSet для хранения уникального элемента.
- Запустите вложенный цикл с двумя циклами: внешний цикл от 0 до n-2 и внутренний цикл от i+1 до n-1
- Проверьте, присутствует ли сумма i-го и j-го элементов, умноженных на -1, в HashSet или нет.
- Если элемент присутствует в HashSet, выведите триплет, иначе вставьте j-й элемент в HashSet.
function findTriplets(arr, n)
{
var found = false;
for (var i = 0; i < n - 1; i++)
{
// Find all pairs with sum equals to
// "-arr[i]"
var s = new Set();
for (var j = i + 1; j < n; j++)
{
var x = -(arr[i] + arr[j]);
if (s.has(x))
{
document.write( x + " " + arr[i] + " " + arr[j] + "<br>");
found = true;
}
else
s.add(arr[j]);
}
}
if (found == false)
document.write( " No Triplet Found" );
}
Контейнер с наибольшим количеством воды — O(N)
Input: array = [3, 1, 2, 4, 5] Output: 12 Explanation : 5 and 3 are distance 4 apart. So the size of the base = 4. Height of container = min(5, 3) = 3. So total area = 4 * 3 = 12
ГРУБАЯ СИЛА = Временная сложность: O(n²)
function maxArea(A, len)
{
let area = 0;
for (let i = 0; i < len; i++) {
for (let j = i + 1; j < len; j++) {
// Calculating the max area
area = Math.max(area, Math.min(A[j], A[i]) * (j - i));
}
}
return area;
}
Эффективный подход
- Временная сложность: O(n).
Поскольку требуется только один обход массива, временная сложность равна O(n). - Пространственная сложность: O(1).
Дополнительное пространство не требуется, поэтому сложность пространства постоянна.
Алгоритм:
- Сохраните два индекса, first = 0 и last = n-1, и значение max_area, которое хранит максимальную площадь.
- Запустите цикл, пока первый не будет меньше последнего.
- Обновите max_area, указав максимум max_area и min(array[first] , array[last])*(last-first)
- если значение в массиве [первый] больше, чем массив [последний], затем обновить последний как последний - 1 иначе обновить первый как первый + 1
- Распечатайте максимальную площадь.
function maxArea(A, len) {
let l = 0;
let r = len -1;
let area = 0;
while (l < r) {
// Calculating the max area
area = Math.max(area, Math.min(A[l], A[r]) * (r - l));
if (A[l] < A[r])
l += 1;
else
r -= 1;
}
return area;
}
Улавливание дождевой воды
Идея этого подхода заключается в следующем:
Для каждого индекса количество накопленной дождевой воды представляет собой разницу между текущей высотой индекса и минимумом максимальной высоты слева и максимальной высоты справа.
Здесь мы можем использовать подход с двумя указателями, чтобы найти минимум среди левого максимума и правого максимума вероятной самой внешней границы для любого индекса, и повторить итерацию аналогично.
var trap = function(height) {
let total = 0, l = 0, r = height.length - 1;
let leftMax = height[l],
rightMax = height[r];
while (l != r) {
leftMax = Math.max(leftMax, height[l]);
rightMax = Math.max(rightMax, height[r]);
if (height[l] < height[r]) {
total += (Math.min(leftMax, rightMax) - height[l]);
l++;
} else {
total += (Math.min(leftMax, rightMax) - height[r]);
r--;
}
}
return total;
};
Лучшее время для покупки и продажи акций
Временная сложность:O(N). Где N — размер массива цен.
Вспомогательный пробел:O(1). Мы не используем дополнительное пространство.
Input: prices[] = {7, 1, 5, 3, 6, 4]
Output: 5
Explanation:
The lowest price of the stock is on the 2nd day, i.e. price = 1. Starting from the 2nd day, the highest price of the stock is witnessed on the 5th day, i.e. price = 6.
Therefore, maximum possible profit = 6 – 1 = 5.
var maxProfit = function(prices) {
let maxProfit = 0;
let buy = 0, sell = 1;
let i = 1;
while( i < prices.length && sell < prices.length ) {
if( prices[buy] > prices[sell] ) {
buy = sell, sell++;
} else{
profit = prices[sell]-prices[buy];
maxProfit = Math.max(maxProfit , profit);
sell++;
}
i++
}
return maxProfit
};
https://www.geeksforgeeks.org/best-time-to-buy-and-sell-stock/
