Sum of Three Values
Given an array of integers, nums, and an integer value, target, determine if there are any three integers in nums whose sum is equal to the target, that is, nums[i] + nums[j] + nums[k] == target. Return TRUE if three such integers exist in the array. Otherwise, return FALSE.
Given an array of integers, nums, and an integer value, target, determine if there are any three integers in nums whose sum is equal to the target, that is, nums[i] + nums[j] + nums[k] == target. Return TRUE if three such integers exist in the array. Otherwise, return FALSE.
Note
A valid triplet consists of elements with distinct indexes. This means, for the triplet nums[i], nums[j], and nums[k], i ≠ j, i ≠ k, and j ≠ k.
Constraints
- 3 ≤
nums.length≤ 500 - −10³ ≤
nums[i]≤ 10³ - −10³ ≤
target≤ 10³
Examples
Example 1
Input:
nums = [3, 7, 1, 2, 8, 4, 5]
target = 20
Output: True
Example 2
Input:
nums = [-1, 2, 1, 4]
target = 1
Output: False
Example 3
Input:
target = 1
Output: True
Naive Solution Easiest way of solving this if I create three nested loops and check sum of three values is equal to target. Tiime commplexity O(N^3)
Optimized Solution We can use a binary search type technique to solve this problem. We'll start by sorting the array and start iterating from 0 to n-1 here i+1 will be our left pointer and n-2 would be our right pointer.Here we take a ith number and looks for other two digits that could give us this target.
function findSumOfThree(nums, target) {
nums.sort((a, b) => {
return a - b;
});
for (let i = 0; i < nums.length - 2; i++){
let low = i + 1;
let high = nums.length - 1;
while (low < high) {
let triple = nums[i] + nums[low] + nums[high];
if (triple == target) {
return true;
}
else if (triple < target) low++;
else high--;
}
};
return false;
}
Time Complexity: O(N^2)
Space Complexity: O(1)