Find 3 numbers from two arrays equal to a given number M

Question

This is a question from yahoo. Find 3 numbers from two arrays A and B . Input : unsorted arrays A and B. Output: The sets of three numbers which sums to M. There are many kinds of results to meet the demand.

Request: one number from A, the other two from B; or one number from B, the other two from A.The space complexity O(1), make effort to reduce the time complexity.

How to implement and avoid the duplicate tuples? This qustion likes questions from here. But is there some easy method to solve? I want to know how to avoid the duplicate result from two arrays? If we do not sort the arrays, can we implement the algorithm with same demands.

You should show some elements of research. What have you tried ? Is there a time and space complexity target ? You should check http://stackoverflow.com/questions/5630363/find-two-elements-in-an-array-that-sum-to-k — Traklon, Oct 04 '13 at 07:38
It's not even clear whether you want three numbers all equal to `M` or three numbers which sum to `M`. — Henrik, Oct 04 '13 at 08:07
Sorry to describe the question unclearly. Array A and B are not sorted. Sum the three numbers equal to M. The space complexity O(1), make effort to reduce the time complexity. How to implement and avoid the duplicate tuples? — user2780417, Oct 04 '13 at 14:51

score 0 · Answer 1 · answered Oct 04 '13 at 08:15

An easy way to get a unique list to choose from which is not the one selected...

http://jsfiddle.net/jsxzA/

HTML:

Array A:<div id="select_container">
<select id="select_box"></select>
</div>

Array B:<div id="array_B"></div>

Values from B which are not equal to what you selected: <div id="uniques"></div>

javascript:

var arrA = [1, 2, 3, 4];
var arrB = [1, 5, 6, 7];
var BArrLength = arrB.length;
var i;
var selectedFromA;
var uniqueArrB = [];
var selectContainer = $('#select_container');
var htmlString = '';

$.each(arrA, function(index, value){
  htmlString += '<option value="'+value+'">'+value+'</option>';
});

$('#select_box').append('<option></option>'+htmlString);

$.each(arrB, function(index, value){
 $('#array_B').append(value);   
});

$('#select_box').html(htmlString);

$('#select_container').on('change', 'select', function(){
    selectedFromA = $('#select_box option:selected').val();
    $('#uniques').html("");
    for(i = 0; i < BArrLength; i += 1){
        if(arrB[i] != selectedFromA){
            $('#uniques').append(''+arrB[i]);
        }
    }    
});

Find 3 numbers from two arrays equal to a given number M

1 Answers1