- Somme de quatre éléments II
L'objectif est de compter combien de quadruplets (i, j, k, l) vérifient nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0. Une approche naïve en O(n⁴) est inacceptable. On peut regrouper les listes deux à deux pour réduire la copmlexité.
En combinant les deux premières listes, on calcule toutes les sommes possibles et on stocke leur fréquence dans un dictionnaire ou un Counter. Ensuite, pour chaque somme issue des deux dernières listes, on cherche son opposé dans le dictionnaire. La complexité passe ainsi à O(n²).
from collections import Counter
class Solution:
def fourSumCount(self, nums1, nums2, nums3, nums4):
# Fréquences des sommes de nums1 et nums2
freq_ab = Counter(a + b for a in nums1 for b in nums2)
# Pour chaque somme de nums3 et nums4, on ajoute la fréquence de l'opposé
return sum(freq_ab[-c - d] for c in nums3 for d in nums4)
Cette variante utilise Counter pour une écriture plus concise, mais le principe reste identique : on évite de parcourir quatre boucles imbriquées en partitionnant les données.
- Ransom Note (lettre de rançon)
On doit vérifier que chaque caractère de ransomNote apparaît au moins aussi souvent dans magazine. Une solution simple consiste à utiliser un tableau de comptage de taille 26 pour les lettres minuscules.
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
compteur = [0] * 26
# On incrémente pour chaque lettre de la rançon
for ch in ransomNote:
compteur[ord(ch) - ord('a')] += 1
# On décrémente pour chaque lettre du magazine
for ch in magazine:
compteur[ord(ch) - ord('a')] -= 1
# S'il reste un compteur positif, le magazine ne suffit pas
return all(c <= 0 for c in compteur)
On peut aussi exploiter la soustraction de Counter : not (Counter(ransomNote) - Counter(magazine)). Cette expression ne conserve que les lettres dont la fréquence dans ransomNote dépasse celle de magazine.
- 3Sum (somme de trois termes)
Le défi est de trouver tous les triplets uniques dont la somme est nulle. L'approche par double pointeur après tri est la plus efficace en O(n²). On fixe un premier élément i, puis on cherche deux autres éléments left et right tels que la somme totale soit nulle.
Le tri permet de gérer facilement les doublons : on saute les valeurs identiques consécutives pour chaque pointeur. La boucle principale s'arrête dès que le premier élément devient positif, car la somme des deux suivants serait nécessairement positive.
class Solution:
def threeSum(self, nums):
nums.sort()
res = []
n = len(nums)
for i in range(n - 2):
# Si le premier élément est > 0, la somme ne peut plus être nulle
if nums[i] > 0:
break
# Éviter les doublons sur le premier élément
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
res.append([nums[i], nums[left], nums[right]])
# Sauter les doublons pour left et 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
return res
- 4Sum (somme de quatre termes)
On généralise la technique des deux pointeurs pour quatre éléments. On fixe deux indices i et k puis on parcourt le reste avec left et right. La complexité est O(n³).
L’élagage (pruning) est crucial : dès que la somme minimale possible dépasse la cible target avec des valeurs positives, on peut interrompre la boucle. Attention, en présence de nombres négatifs, il faut utiliser break plutôt que return pour ne pas ignorer des combinaisons ultérieures plus petites.
class Solution:
def fourSum(self, nums, target):
nums.sort()
res = []
n = len(nums)
for i in range(n - 3):
# Élagage : plus aucune combinaison possible
if nums[i] > 0 and nums[i] > target and target > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
for k in range(i + 1, n - 2):
# Attention : on ne peut pas return, car des nombres négatifs pourraient encore convenir
if nums[i] + nums[k] > 0 and nums[i] + nums[k] > target and target > 0:
break
if k > i + 1 and nums[k] == nums[k - 1]:
continue
left, right = k + 1, n - 1
while left < right:
total = nums[i] + nums[k] + nums[left] + nums[right]
if total < target:
left += 1
elif total > target:
right -= 1
else:
res.append([nums[i], nums[k], 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
return res