TwoSum之Java實現(xiàn)-創(chuàng)新互聯(lián)

一、題目

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].

成都創(chuàng)新互聯(lián)基于成都重慶香港及美國等地區(qū)分布式IDC機房數(shù)據(jù)中心構(gòu)建的電信大帶寬，聯(lián)通大帶寬，移動大帶寬，多線BGP大帶寬租用,是為眾多客戶提供專業(yè)服務(wù)器托管報價，主機托管價格性價比高，為金融證券行業(yè)成都IDC機房托管，ai人工智能服務(wù)器托管提供bgp線路100M獨享，G口帶寬及機柜租用的專業(yè)成都idc公司。

二、題目理解

給定一個整型數(shù)組以及一個目標(biāo)值，求數(shù)組中兩個相加等于目標(biāo)值的元素的索引。此題假設(shè)給定的數(shù)組中一定有兩個元素相加等于目標(biāo)值。

三、實現(xiàn)代碼

1、第一種實現(xiàn)方式
使用暴力搜索的方式，用雙層for循環(huán)遍歷數(shù)組，拿數(shù)組的每一個元素與其他元素相加之后與目標(biāo)值進(jìn)行對比，找出符合要求的兩個元素。
實現(xiàn)代碼如下：

public int[] twoSum01(int[] nums, int target) {
    int[] result = new int[2];
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                result[0] = i;
                result[1] = j;
                break;
            }
        }
    }
    return result;
}

2、第二種實現(xiàn)方式
第一種實現(xiàn)方式在最壞的情況下的時間復(fù)雜度為O(n2)，執(zhí)行時間較長，不是一種比較好的實現(xiàn)方式，下面是第二種實現(xiàn)方法。
定義一個Map，遍歷數(shù)組，每次都用目標(biāo)值減去數(shù)組當(dāng)前值得到差值temp，并判斷temp是否存在于Map中，如不存在，則將數(shù)組當(dāng)前值和索引存入Map中；如存在，則取出temp對應(yīng)的索引值。
實現(xiàn)代碼如下：

public int[] twoSum02(int[] nums, int target) {
    HashMap<Integer, Integer> tempMap = new HashMap<Integer, Integer>();
    int[] resultArr = new int[2];
    for(int i = 0; i < nums.length; i++) {
        // 用target減去數(shù)組當(dāng)前值
        int temp = target - nums[i];
        // 判斷HashMap中是否包含temp
        if(tempMap.get(temp) != null) {
            resultArr[0] = tempMap.get(temp);
            resultArr[1] = i;
            break;
        } else {
            tempMap.put(nums[i], i);        // 如不包含，就將當(dāng)前值存入Map中
        }
    }
    return resultArr;
}

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。

當(dāng)前文章：TwoSum之Java實現(xiàn)-創(chuàng)新互聯(lián)
文章出自：http://muchs.cn/article18/dpecdp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供自適應(yīng)網(wǎng)站、響應(yīng)式網(wǎng)站、電子商務(wù)、面包屑導(dǎo)航、微信公眾號、移動網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)