Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a list of integers nums and an integer target, return the number of triples i < j < k that exist such that nums[i] + nums[j] + nums[k] < target.
Constraints
n ≤ 1,000 where n is the length of nums
Example 1
Input
nums = [-3, 5, 3, 2, 7]
target = 9
Output
5
Explanation
Here are the different triples’ values:
-3 + 5 + 3 = 5
-3 + 5 + 2 = 4
-3 + 3 + 2 = 2
-3 + 3 + 7 = 7
-3 + 2 + 7 = 6
Four Sum Less Than Target
We can bruteforce all triplets – which takes O(N^3) time:
1 2 3 4 5 6 7 8 9 10 | class Solution: def solve(self, nums, target): ans = 0 n = len(nums) for i in range(n): for j in range(i + 1, n): for k in range(j + 1, n): if nums[i] + nums[j] + nums[k] < target: ans += 1 return ans |
class Solution:
def solve(self, nums, target):
ans = 0
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if nums[i] + nums[j] + nums[k] < target:
ans += 1
return ansAlternatively, we can bruteforce first pair, and apply two pointer algorithm on the remaining. This requires sorting which takes O(NLogN). When we have the sum less than target, we know there are R-L triplets for current choices:
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution: def solve(self, nums, target): nums.sort() ans = 0 for i in range(len(nums)): j, k = i + 1, len(nums) - 1 while j < k: if nums[i] + nums[j] + nums[k] < target: ans += k - j # add triplet sum j += 1 else: k -= 1 return ans |
class Solution:
def solve(self, nums, target):
nums.sort()
ans = 0
for i in range(len(nums)):
j, k = i + 1, len(nums) - 1
while j < k:
if nums[i] + nums[j] + nums[k] < target:
ans += k - j # add triplet sum
j += 1
else:
k -= 1
return ansThe space complexity is O(1) constant.
Two Pointer Algorithm to Count the Sum of Three Numbers Less than Target
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: BASH Script to Compute the Average Ping to a Domain
Next Post: Using ADODB to Query SQLite in VBScript
