तीन संख्याओं का लक्ष्य योग ढूँढना - नेस्टेड छोरों का अनुकूलन

एक स्पष्ट अनुकूलन तीसरे नेस्टेड लूप से ठीक पहले दो पहली संख्याओं के योग का पूर्व-गणना करना है। फिर तीसरे लूप में तुलना करें यदि वह संख्या तीसरी पुनरावृत्त संख्या के विपरीत है।

दूसरा अनुकूलन इस तथ्य का लाभ उठाना है कि आपके आइटम सॉर्ट किए गए हैं और तीसरे लूप के बजाय शेष सरणी में दो पहले शब्दों के योग के वास्तविक नकारात्मक के लिए बाइनरी खोज का उपयोग करें। यह दूसरा अनुकूलन O(N3) से O(N2LogN) तक जटिलता लाता है

जो तीसरे अनुकूलन की ओर जाता है, जिसके लिए आप एक मानचित्र में योग को कुंजी और मूल्य के रूप में संग्रहीत कर सकते हैं, विभिन्न जोड़े की एक सरणी जो योग के योग के लिए है ताकि हर बार जब आप बाइनरी खोज को फिर से संचालित करना चाहते हैं, तो पहले आप जांच लें यदि उस मानचित्र में योग पहले से मौजूद है और यदि ऐसा होता है तो आप मानचित्र में उस योग के सूचकांक में पाए जाने वाले प्रत्येक जोड़े के संयोजन को ऋणात्मक योग के साथ जोड़ सकते हैं।

var threeSum = function(unsortedNums) {
    const nums = unsortedNums.sort();

    if(nums.length && (nums[0] > 0 || nums[nums.length-1] < 0)) {
        return [];
    }

    const result = new Map();

    for(let i=0; i < nums.length; i++) {
        for(let z=i+1; z < nums.length; z++) {
            for(let q=z+1; q < nums.length; q++) {
                if(nums[i]+nums[z]+nums[q] === 0) {
                    const toAdd = [nums[i], nums[z], nums[q]];            
                    const toAddStr = toAdd.join(',');

                    if(!result.has(toAddStr)) {
                        result.set(toAddStr, toAdd);
                    }
                }
            }
        }
    }

    return Array.from(result.values());
};

OP का समाधान बिना किसी अतिरिक्त संग्रहण के O(N³) समय में चलता है।

लापता तत्व को खोजने के लिए क्लासिक "हैश टेबल का उपयोग करें" समाधान O(N) स्टोरेज के साथ इसे O(N²) समय तक ला सकता है।

समाधान में किसी वस्तु का उपयोग करके एक संख्या मानचित्र बनाना शामिल है। (आप मानचित्र ऑब्जेक्ट का भी उपयोग कर सकते हैं, लेकिन तब आप ++ और -- ऑपरेटरों के साथ उतने अभिव्यंजक नहीं हो सकते)। फिर सभी जोड़ियों का मूल्यांकन करने के लिए बस एक साधारण लूप और इनर लूप। प्रत्येक जोड़े के लिए, पता करें कि क्या उन युग्मों का ऋणात्मक योग मानचित्र में है।

function threeSum(nums) {

    var nummap = {};    // map a value to the number of ocurrances in nums
    var solutions = new Set(); // map of solutions as strings

    // map each value in nums into the number map
    nums.forEach((val) => {
        var k = nummap[val] ? nummap[val] : 0; // k is the number of times val appears in nummap
        nummap[val] = k+1; // increment by 1 and update
    });

    // for each pair of numbers, see if we can find a solution the number map
    for (let i = 0; i < nums.length; i++) {

        var ival = nums[i];
        nummap[ival]--;

        for (let j = i+1; j < nums.length; j++) {
            var jval = nums[j];
            nummap[jval]--;

            var target = -(ival + jval); // this could compute "-0", but it works itself out since 0==-0 and toString will strip the negative off

            // if target is in the number map, we have a solution
            if (nummap[target]) {

                // sort this three sum solution and insert into map of available solutions
                // we do this to filter out duplicate solutions
                var tmp = [];
                tmp[0] = ival;
                tmp[1] = jval;
                tmp[2] = target;

                tmp.sort();
                solutions.add(tmp.toString());
            }

            nummap[jval]++; // restore original instance count in nummap
        }
        nummap[ival]--;
    }

    for (s of solutions.keys()) {
        console.log(s);
    }

}

threeSum([9,8,7,-15, -9,0]);