php算法題：兩數之和

Ververica 發布于2019-07-01 12:43 / 3700人閱讀

摘要：一兩遍循環，暴力破解代碼如下時間復雜度提交，結果執行時間。。。。。可以說龜速了二兩遍這個方法是看了的解決方案，但它是代碼，開始不知道，其實的數組就是實現的，后面看了下面兩片文章的介紹，才理解，解決的。

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

一、兩遍循環，暴力破解

代碼如下

function twoSum($nums, $target) {
        for($i=0;$i
時間復雜度 O(n^2 )
提交，結果執行時間1968 ms。。。。。
可以說龜速了
二、兩遍hash
這個方法是看了leetcode的解決方案，但它是java代碼，開始不知道，其實php的數組就是hash實現的，后面看了下面兩片文章的介紹，才理解，解決的。
https://www.cnblogs.com/s-b-b...
https://www.cnblogs.com/shang...
代碼如下
function twoSum2(array $nums , $target)
{
    $res = [];
    $nums_match = [];
    foreach ($nums as $nums_k => $nums_v){
        if(!isset($nums_match[$target-$nums_v])){
            $nums_match[$target-$nums_v] = $nums_k;
        }
    }
    
    foreach ($nums as $nums_k => $nums_v){
        if (isset($nums_match[$nums_v]) && $nums_match[$nums_v] != $nums_k) {
            $res[] = $nums_k;
            $res[] = $nums_match[$nums_v];
            return $res;
        }
    }
}
時間復雜度O(n)
執行時間24 ms    ，提升很大
三、一遍hash
這是在兩邊hash的基礎上進行的優化
代碼如下
function twoSum($nums, $target) {
        $nums_match = [];
        foreach ($nums as $nums_k => $nums_v){
            if((isset($nums_match[$target-$nums_v]))){
                return array($nums_match[$target-$nums_v],$nums_k);
            }
            $nums_match[$nums_v] = $nums_k;
        }

    }
時間復雜度O(n)
執行時間16 ms

云服務器 GPU云服務器回文數之和 php javascript算法題字符串算法題最難的算法題

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/31350.html

算法題-兩數之和

摘要：題目描述給出兩個非空的鏈表用來表示兩個非負的整數。如果，我們將這兩個數相加起來，則會返回一個新的鏈表來表示它們的和。您可以假設除了數字之外，這兩個數都不會以開頭。題目描述：給出兩個非空的鏈表用來表示兩個非負的整數。其中，它們各自的位數是按照逆序的方式存儲的，并且它們的每個節點只能存儲一位數字。如果，我們將這兩個數相加起來，則會返回一個新的鏈表來表示它們的和。您可以假設除...

Vicky 2019-08-26 10:29 評論0 收藏0
【前端來刷LeetCode】兩數之和與兩數相加

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

BLUE 2019-08-26 13:53 評論0 收藏0
【刷算法】LeetCode- 兩數之和

摘要：題目描述給定一個整數數組和一個目標值，找出數組中和為目標值的兩個數。你可以假設每個輸入只對應一種答案，且同樣的元素不能被重復利用。題目描述給定一個整數數組和一個目標值，找出數組中和為目標值的兩個數。你可以假設每個輸入只對應一種答案，且同樣的元素不能被重復利用。示例: 給定 nums = [2, 7, 11, 15], target = 9 因為 nums[0] + nums[...

superw 2019-08-23 10:27 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
LeetCode 167：兩數之和 II - 輸入有序數組 Two Sum II - Input a

摘要：公眾號愛寫給定一個已按照升序排列的有序數組，找到兩個數使得它們相加之和等于目標數。函數應該返回這兩個下標值和，其中必須小于。示例輸入輸出解釋與之和等于目標數。公眾號：愛寫bug（ID：icodebugs）給定一個已按照升序排列的有序數組，找到兩個數使得它們相加之和等于目標數。函數應該返回這兩個下標值 index1 和 index2，其中 index1 必須小于 index2。...

張春雷 2019-08-16 18:29 評論0 收藏0