Two Pointers: Sum of Three Values

by Raul Bojalil

HTML

<p data-id="e8f707a501b76c4e2de0f5351eb6a2da">Given an array of integers, <code>nums</code>, and an integer value, <code>target</code>, determine if there are any three integers in <code>nums</code> whose sum is equal to the <code>target</code>, that is, <code>nums[i] + nums[j] + nums[k] == target</code>. Return TRUE if three such integers exist in the array. Otherwise, return FALSE.</p>

<div class="markdownViewer select-text  markdown-default markdown-table markdown-viewer markdown-viewer-heading" role="none"><h4 class="hover-anchor" id="Solution-summary" data-id="87bbf7e35fe27305a7087e59419168c3">Solution summary<a href="#Solution-summary"><span class="anchor-link">#</span></a></h4>
<p data-id="d1c41a73bea431eabec97c31b3b47129">First, sort the array in ascending order. To find a triplet whose sum is equal to the target value, loop through the entire array. In each iteration:</p>
<ol data-id="eb7bde2580f9fed943c3288da5d85a6e">
<li>
<p>Store the current array element and set up two pointers (<code>low</code> and <code>high</code>) to find the other two elements that complete the required triplet.</p>
<ul>
<li>
<p>The <code>low</code> pointer is set to the current loop’s index + 1.</p>
</li>
<li>
<p>The <code>high</code> is set to the last index of the array.</p>
</li>
</ul>
</li>
<li>
<p>Calculate the sum of array elements pointed to by the current loop’s index and the <code>low</code> and <code>high</code> pointers.</p>
</li>
<li>
<p>If the sum is equal to <code>target</code>, return TRUE.</p>
</li>
<li>
<p>If the sum is less than <code>target</code>, move the <code>low</code> pointer forward.</p>
</li>
<li>
<p>If the sum is greater than <code>target</code>, move the <code>high</code> pointer backward.</p>
</li>
</ol>
<p data-id="cce640b677f30613abe91ef4cd703bcd">Repeat until the loop has processed the entire array. If, after processing the entire array, we don’t find any triplet that matches our requirement, we return FALSE.</p>
<h4 class="hover-anchor"...

JavaScript

function findSumOfThree(nums, target) {
  nums.sort((a,b) => {
  	return a - b;
  });
  
  for (var i=0; i < nums.length - 2; i++) {
  	let lp = i+1;
    let rp = nums.length - 1;
    
    while (lp < rp) {
      let sum = nums[i] + nums[lp] + nums[rp];

      if (sum == target) {
        return true;
      }
      else if (sum < target) lp++;
      else rp--;
    }
  }
  
  return false;
}

let numsLists = [
  [3, 7, 1, 2, 8, 4, 5],
  [-1, 2, 1, -4, 5, -3],
  [2, 3, 4, 1, 7, 9],
  [1, -1, 0],
  [2, 4, 2, 7, 6, 3, 1],
];

let testLists = [10, 7, 20, -1, 8];

numsLists.map((numList, i) => {
  console.log(i + 1 + ".\tInput array:", numsLists[i]);

  if (findSumOfThree(numsLists[i], testLists[i]))
    console.log("\tSum for", testLists[i], "exists");
  else console.log("\tSum for", testLists[i], "does not exist");

  console.log("-".repeat(100));
});