LeetCode - 4Sum

@godblessrecki · Регистрация: 22.03.2024

Студворк — интернет-сервис помощи студентам

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.

Написал такой код, он верный, но testcase с большим количеством чисел выдает, что время, за которое программа должна быть выполнена, превышает нормы ("Time Limit Exceeded").
Вот TestCase:
nums =
[10,10,10,10,10,10,10,10,10,10,10,10,10,1 0,10,10,10,10,10,10,20,20,20,20,20,20,20 ,20,20,20,20,20,20,20,20,20,20,20,20,20, 30,30,30,30,30,30,30,30,30,30,30,30,30,3 0,30,30,30,30,30,30,40,40,40,40,40,40,40 ,40,40,40,40,40,40,40,40,40,40,40,40,40, 50,50,50,50,50,50,50,50,50,50,50,50,50,5 0,50,50,50,50,50,50,60,60,60,60,60,60,60 ,60,60,60,60,60,60,60,60,60,60,60,60,60, 70,70,70,70,70,70,70,70,70,70,70,70,70,7 0,70,70,70,70,70,70,80,80,80,80,80,80,80 ,80,80,80,80,80,80,80,80,80,80,80,80,80, 90,90,90,90,90,90,90,90,90,90,90,90,90,9 0,90,90,90,90,90,90]
target =
200

Как можно оптимизировать мой код?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        List = list()
        for i in range(len(nums)):
            for a in range(i+1, len(nums)):
                for y in range(a+1, len(nums)):
                    for z in range(y+1, len(nums)):
                        if nums[i] + nums[a] + nums[y] + nums[z] == target:
                            last = [nums[i], nums[a], nums[y], nums[z]]
                            List.append(last)
                            for j in range(len(List)-1):
                                    if sorted(last) == sorted(List[j]):
                                        List.pop()
 
        return List

@mirasmatras · 22.03.2024, 18:32

Какое целевое время?

Добавлено через 8 минут

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
    def fourSum(self, nums: list[int], target: int) -> list[list[int]]:
        nums.sort()
        n = len(nums)
        quadruplets = []
 
        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
 
            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
 
                left = j + 1
                right = n - 1
 
                while left < right:
                    total = nums[i] + nums[j] + nums[left] + nums[right]
 
                    if total == target:
                        quadruplets.append([nums[i], nums[j], nums[left], nums[right]])
                        while left < right and nums[left] == nums[left + 1]:
                            left += 1
                        while left < right and nums[right] == nums[right - 1]:
                            right -= 1
                        left += 1
                        right -= 1
                    elif total < target:
                        left += 1
                    else:
                        right -= 1
 
        return quadruplets
 
 
 
nums = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,20,20,20,20,20,20,20 ,20,20,20,20,20,20,20,20,20,20,20,20,20,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40,40, 50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,60,60,60,60,60,60,60 ,60,60,60,60,60,60,60,60,60,60,60,60,60,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,70,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80,80, 90,90,90,90,90,90,90,90,90,90,90,90,90,90,90,90,90,90,90,90]
target = 200
solution = Solution()
print(solution.fourSum(nums, target))

Python
1
2
# Выводит:
[[10, 10, 90, 90], [10, 20, 80, 90], [10, 30, 70, 90], [10, 30, 80, 80], [10, 40, 60, 90], [10, 40, 70, 80], [10, 50, 50, 90], [10, 50, 60, 80], [10, 50, 70, 70], [10, 60, 60, 70], [20, 20, 70, 90], [20, 20, 80, 80], [20, 30, 60, 90], [20, 30, 70, 80], [20, 40, 50, 90], [20, 40, 60, 80], [20, 40, 70, 70], [20, 50, 50, 80], [20, 50, 60, 70], [20, 60, 60, 60], [30, 30, 50, 90], [30, 30, 60, 80], [30, 30, 70, 70], [30, 40, 40, 90], [30, 40, 50, 80], [30, 40, 60, 70], [30, 50, 50, 70], [30, 50, 60, 60], [40, 40, 40, 80], [40, 40, 50, 70], [40, 40, 60, 60], [40, 50, 50, 60], [50, 50, 50, 50]]

Я думаю, что проблема в том, что ваш код использует четыре вложенных цикла, что понижает его эффективность (O( $https://www.cyberforum.ru/cgi-bin/latex.cgi?{n}^{4}$ )). Я попытался понизить, результат, я думаю, верный (не запускал ваш код, если честно).

Добавлено через 1 час 53 минуты

Не по теме:

Если помогло, отметьте как правильный ответ, пожалуйста

@iSmokeJC · 22.03.2024, 19:01

Сообщение от mirasmatras

отметьте как правильный ответ, пожалуйста

Перечитайте Правила форума, пожалуйста

Рыжий Лис · 23.03.2024, 09:50

Python
1
2
3
4
5
6
7
8
def zipp_storm(nums: list[int]) -> list[int]:
    result = []
    for val, cnt in Counter(nums).items():
        cnt = min(cnt, 4)
        result += [val] * cnt
    return result
    
nums = zipp_storm(nums)

Добавлено через 1 минуту
Даже так:

Python
1
2
3
4
5
6
7
def zipp_storm(nums: list[int], target: int)) -> list[int]:
    result = []
    for val, cnt in Counter(nums).items():
        if val <= target:
            cnt = min(cnt, 4)
            result += [val] * cnt
    return result

Новые блоги и статьи Все статьи Все блоги /
Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI
Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .