⬅ Previous Topic
Sort an Array of 0s, 1s, and 2sNext Topic ⮕
Three Sum Problem⬅ Previous Topic
Sort an Array of 0s, 1s, and 2sNext Topic ⮕
Three Sum ProblemTopic Contents
Given an array of integers nums
and a target number, your task is to find the indices of two numbers in the array that add up exactly to the target.
If no such pair exists, return an empty result.
nums
and a target
.i
from 0
to n-2
(where n
is the array length), iterate over every element with index j
from i+1
to n
-1.(i, j)
, calculate the sum of nums[i]
and nums[j]
.[i, j]
.class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums) - 1):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(1) | If the required pair is found in the very first iteration. |
Average Case | O(n^2) | Each element is compared with every other element after it, resulting in a nested loop. |
Worst Case | O(n^2) | In the worst case, all pairs must be checked before a match is found or concluded none exists. |
O(1)
Explanation: No additional data structures are used beyond a few variables.
⬅ Previous Topic
Sort an Array of 0s, 1s, and 2sNext Topic ⮕
Three Sum ProblemYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.