【刷算法】和為S的兩個(gè)數(shù)字

Dr_Noooo 發(fā)布于2019-08-22 18:14 / 3001人閱讀

摘要：題目描述輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字，在數(shù)組中查找兩個(gè)數(shù)，是的他們的和正好是，如果有多對(duì)數(shù)字的和等于，輸出兩個(gè)數(shù)的乘積最小的。解題思路數(shù)組是遞增的，且給的數(shù)字是固定的，那就可以用夾逼法。和碰頭了說(shuō)明該結(jié)束了。

題目描述

輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字S，在數(shù)組中查找兩個(gè)數(shù)，是的他們的和正好是S，如果有多對(duì)數(shù)字的和等于S，輸出兩個(gè)數(shù)的乘積最小的。

解題思路

數(shù)組是遞增的，且給的數(shù)字S是固定的，那就可以用夾逼法。
兩個(gè)指針left和right從數(shù)組的兩端開(kāi)始，要是left和right指向的數(shù)字之和大于S，說(shuō)明right得向左移動(dòng)一下，因?yàn)閞ight的左邊是比它小的數(shù)字；要是left的right指向的數(shù)字之和小于S，說(shuō)明left得向右邊移動(dòng)一下，因?yàn)閘eft的右邊是比它大的數(shù)字。left和right碰頭了說(shuō)明該結(jié)束了。

代碼實(shí)現(xiàn)

function FindNumbersWithSum(array, sum)
{
    if(!array || array.length < 2 || sum === 0)
        return [];
    var left = 0;
    var right = array.length-1;
    var res = [];
    while(left !== right) {
        var curSum = array[left]+array[right];
        if(curSum === sum){
            res.push(array[left]);
            res.push( array[right]);
            break;
        }
        else if(curSum > sum)
            right--;
        else 
            left++
    }
    return res;
}

GPU云服務(wù)器云服務(wù)器數(shù)字水印算法兩個(gè)數(shù)字數(shù)字引擎刷云主機(jī) 數(shù)字中國(guó)刷云主機(jī)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/95644.html

相關(guān)文章

【刷算法】二叉樹(shù)中和為某一值的路徑

摘要：題目描述輸入一顆二叉樹(shù)和一個(gè)整數(shù)，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑。思路二叉樹(shù)的大多數(shù)問(wèn)題可以使用遞歸來(lái)解決，本題亦如此。題目描述輸入一顆二叉樹(shù)和一個(gè)整數(shù)，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑。思路二叉樹(shù)的大多數(shù)問(wèn)題可以使用...

zxhaaa 2019-08-22 18:21 評(píng)論0 收藏0
小李飛刀：刷題第四彈！

摘要：第二題羅馬數(shù)字轉(zhuǎn)整數(shù)難度簡(jiǎn)單羅馬數(shù)字包含以下七種字符，，，，，和。字符數(shù)值例如，羅馬數(shù)字寫(xiě)做，即為兩個(gè)并列的。通常情況下，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊。給定一個(gè)羅馬數(shù)字，將其轉(zhuǎn)換成整數(shù)。隨便說(shuō)點(diǎn)啥 TIME:2019-02-01昨晚其實(shí)刷了題來(lái)著，但是沒(méi)有解出來(lái)，哭泣！但是，今天重新寫(xiě)了下，解出來(lái)咯~所以今天的題量要增加咯~我會(huì)加油的！第一題 14. 最長(zhǎng)公共前綴難度：簡(jiǎn)單 ...

luffyZh 2019-07-31 10:02 評(píng)論0 收藏0
leetcode494. Target Sum

摘要：為了尋找合適的正負(fù)號(hào)賦值，我們其實(shí)可以將數(shù)組分為兩個(gè)子集，其中一個(gè)子集中的數(shù)字都被賦予了正號(hào)，而另一個(gè)子集中的數(shù)字都被賦予了負(fù)號(hào)。如果二者的和不是一個(gè)偶數(shù)，就一定無(wú)法找到這樣的正負(fù)號(hào)集合使得其結(jié)果為。題目要求 You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now yo...

RobinTang 2019-08-15 14:32 評(píng)論0 收藏0
leetCode算法-268（缺失數(shù)字）

摘要：給定一個(gè)包含中個(gè)數(shù)的序列，找出中沒(méi)有出現(xiàn)在序列中的那個(gè)數(shù)。求合法開(kāi)始之前我先說(shuō)一下我的思路個(gè)有序數(shù)字累加和，數(shù)學(xué)里邊是有公式的，我們重溫一下推導(dǎo)過(guò)程。給定一個(gè)包含 0, 1, 2, ..., n 中 n 個(gè)數(shù)的序列，找出 0 .. n 中沒(méi)有出現(xiàn)在序列中的那個(gè)數(shù)。示例 1: 輸入: [3,0,1]輸出: 2示例 2: 輸入: [9,6,4,2,3,5,7,0,1]輸出: 8 下面我...

geekzhou 2019-08-23 15:06 評(píng)論0 收藏0
【前端來(lái)刷LeetCode】?jī)蓴?shù)之和與兩數(shù)相加

摘要：給定表，存在函數(shù)，對(duì)任意給定的關(guān)鍵字值，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址，則稱(chēng)表為哈希表，函數(shù)為哈希函數(shù)。而中的對(duì)象就是基于哈希表結(jié)構(gòu)，所以我們構(gòu)造一個(gè)對(duì)象即可，是當(dāng)前遍歷到的值，是其與目標(biāo)值的差。大部分玩前端的小伙伴，在算法上都相對(duì)要薄弱些，畢竟調(diào)樣式、調(diào)兼容就夠掉頭發(fā)的了，哪還有多余的頭發(fā)再去折騰。確實(shí)在前端中需要使用到算法的地方是比較少，但若要往高級(jí)方向發(fā)展，...

BLUE 2019-08-26 13:53 評(píng)論0 收藏0