What is the best way to identify a trio of items in an array whose combined total matches a specific target sum?

Question

What is the best way to identify a trio of items in an array whose combined total matches a specific target sum?

I am currently utilizing three loops to tackle this problem, but the complexity is O(n3). Is there a way to achieve this with a lower complexity level?

Sharing a JS Fiddle code snippet for the three loops approach:

var arr = [1, 2, 3, 4, 5, 6, 7, 8];
var sum = 8;
find(arr, sum);

function find(arr, sum) {
  var found = false;
  for (var x = 0; x < arr.length - 3; x++) {
    for (var y = x + 1; y < arr.length - 2; y++) {
      for (var z = y + 1; z < arr.length; z++) {
        if (arr[x] + arr[y] + arr[z] == sum) {
          found = true;
          break;
        }
      }
    }
  }
  if (found) {
    console.log("found");
  } else {
    console.log("not found");
  }
}

javascript arrays

Answer 1

Answer №1

A potential solution involves utilizing a hash table and implementing two loops - one for iterating through the array and another for calculating the sum of two items.

function find(array, sum) {
    var hash = Object.create(null);
    return array.some((v, i, a) => {
        a.slice(0, i).forEach(w => hash[v + w] = true);
        return hash[sum - v];
    });
}

console.log(find([1, 2, 3, 4, 5, 6, 7, 8], 8));
console.log(find([1, 2, 3, 4, 5, 6, 7, 8], 42));

If you prefer a more functional approach using a closure with a Set to handle the sum of two values, the following code snippet can also be effective.

function find(array, sum) {
    return array.some(
        (s => (v, i, a) => a.slice(0, i).reduce((t, w) => t.add(v + w), s).has(sum - v))
        (new Set)
    );
}

console.log(find([1, 2, 3, 4, 5, 6, 7, 8], 8));
console.log(find([1, 2, 3, 4, 5, 6, 7, 8], 42));

Answer 2

A potential solution involves utilizing a hash table and implementing two loops - one for iterating through the array and another for calculating the sum of two items.

function find(array, sum) {
    var hash = Object.create(null);
    return array.some((v, i, a) => {
        a.slice(0, i).forEach(w => hash[v + w] = true);
        return hash[sum - v];
    });
}

console.log(find([1, 2, 3, 4, 5, 6, 7, 8], 8));
console.log(find([1, 2, 3, 4, 5, 6, 7, 8], 42));

If you prefer a more functional approach using a closure with a Set to handle the sum of two values, the following code snippet can also be effective.

function find(array, sum) {
    return array.some(
        (s => (v, i, a) => a.slice(0, i).reduce((t, w) => t.add(v + w), s).has(sum - v))
        (new Set)
    );
}

console.log(find([1, 2, 3, 4, 5, 6, 7, 8], 8));
console.log(find([1, 2, 3, 4, 5, 6, 7, 8], 42));

What is the best way to identify a trio of items in an array whose combined total matches a specific target sum?

Answer №1

Similar questions

Best method for converting List of Objects to byte array in c# for efficient serialization and deserialization

Using Raycaster in ThreeJS to pick out faces from models loaded with STL Loader

Angular authentication function not invoked

What could be causing my Three.js code to fail during testing?

Error encountered in ASP.NET MVC application when using jQuery POST method: data is null

Prevent the browser from autofilling password information in a React Material UI textfield when it is in focus

Error: Module not found - Imported Node Module

Is there a way to link to mouseover and mouseleave actions while utilizing ng-options?

What could be causing my node-statsd client script to not terminate?

Leveraging TypeScript's declaration file

Error encountered: `unexpected token within ES6 map() function`

React does not trigger a re-render when dynamically generated buttons are created

The life cycle of the request/response object in Express.js when using callbacks

What are the steps to implement the "render" function from one class into another class within three.js?

Struggling to access data from a multi-dimensional array within a SwiftUI view

How much memory is being used by a loop script?

Is it possible to configure npm install to install "bin" executables directly into the local node_modules directory (rather than the .bin directory)?

How to display only a portion of content using UI Bootstrap collapse feature

JavaScript detecting improper XHTML syntax

Exploring the Power of Elasticsearch with Datatables