LC: 259. 3Sum Smaller
https://leetcode.com/problems/3sum-smaller/
259. 3Sum Smaller
Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
Example 1:
Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]Example 2:
Input: nums = [], target = 0
Output: 0Example 3:
Input: nums = [0], target = 0
Output: 0Constraints:
n == nums.length0 <= n <= 3500-100 <= nums[i] <= 100-100 <= target <= 100
The Essence:
Dieses Problem lässt sich tatsächlich auf ein “2 Sum”-Problem reduzieren:
Das Addieren von 3 Zahlen, die kleiner als ein bestimmter Wert sind, ist gleichbedeutend damit, eine dieser Zahlen auszuwählen, sie vom Zielwert zu subtrahieren und einen neuen Zielwert für die andere 2 zu bekommen.
Man kann also das Array aufsteigend sortieren und dann von den kleinsten Zahlen anfangend für die neue Zielwerte entsprechende Zahlenpaare suchen.
Details:
Die zweite Zahl wird als die nächste kleine Zahl gewählt. Jedoch soll die dritte Zahl zuerst die größte Zahl sein. Wenn der Zielwert für die größte Zahl gilt, dann gilt es auch für kleinere Zahlenkombinationen.
Solution(s): The implementations can be found here:
Default Code:
Last updated