Была эта проблема, которая требовала вернуть все уникальные триплеты элементов массива, сумма которых равна нулю (перестановка мест двух элементов в триплете не считается уникальной).
Я придумал следующий код:
function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length; i++) {
// skipping duplicates
if (i !== 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const s = nums[i] + nums[left] + nums[right];
// too small; move to the right
if (s < 0) left++;
// too big; move to the left
else if (s > 0) right--;
// bingo
else {
result.push([nums[i], nums[left], nums[right]]);
//skipping duplicates
while (left + 1 < right && nums[left] === nums[left + 1]) left++;
while (right - 1 > left && nums[right] === nums[right - 1]) right--;
left++;
right--;
}
}
}
return result;
};
// expected output: [[-4,-2,6],[-4,0,4],[-4,1,3],[-4,2,2],[-2,-2,4],[-2,0,2]]
console.log(threeSum([-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6]))Я думаю, что временная сложность составляет O(n^2). В начале есть сортировка, которая, как мы предполагаем, составляет O(n log n), а вложенный цикл работает примерно (n^2)/2 раз, что преобразуется в О(n^2). Таким образом, в конце у нас остается O(n log n + n^2), и, поскольку n log n имеет меньшую степень, он удаляется, оставляя нас с O(n^2).
Я не совсем уверен в пространственной сложности, но интуитивно думаю, что это O(n).
Не могли бы вы исправить/подтвердить мои рассуждения/догадки о пространственно-временной сложности?
