兩數(shù)之和問題各變種多解法小結(jié)

lentoo 發(fā)布于2019-08-16 10:34 / 520人閱讀

摘要：兩數(shù)之和問題各變種多解法小結(jié)聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處兩數(shù)之和等于題目大意給出未排序數(shù)組和指定目標(biāo)，返回數(shù)組中兩數(shù)之和的組合元素下標(biāo)要求下標(biāo)從開始，而且，保證題目中有且只有個可行解解法暴力時間復(fù)雜度求解解題思路暴力二重循環(huán)求解

兩數(shù)之和問題各變種多解法小結(jié) 聲明

文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處：
[1] https://segmentfault.com/u/yzwall
[2] blog.csdn.net/j_dark/

LintCode_56：兩數(shù)之和等于target

題目大意：給出未排序數(shù)組nums和指定目標(biāo)target，返回數(shù)組中兩數(shù)之和$= target$的組合元素下標(biāo)[index1, index2], 要求下標(biāo)從1開始，而且$index1 < index2$，保證題目中有且只有1個可行解；

解法1：暴力$O(n^2)$時間復(fù)雜度求解

解題思路：暴力二重循環(huán)求解；
復(fù)雜度分析：時間復(fù)雜度$O(n^2)$，空間復(fù)雜度$O(1)$

/**
 * 解法1:時間復(fù)雜度O(n^2)，空間復(fù)雜度O(1)
 * 遍歷求兩數(shù)之和等于target，返回兩數(shù)下標(biāo)（從1開始）
 * http://www.lintcode.com/zh-cn/problem/two-sum/
 * @author yzwall
 */
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] results = 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) {
                    results[0] = i + 1;
                    results[1] = j + 1;
                    return results;
                }
            }
        }
        return results;
    }
}

解法2：HashMap $O(n)$時間復(fù)雜度求解

解題思路：耗費(fèi)$O(n)$空間構(gòu)造哈希表，遍歷數(shù)組每個元素nums[i]，哈希表對應(yīng)存儲，存儲nums[i]期望的“另一半”，一旦哈希表中包含nums[i]，代表“另一半”早已存儲在哈希表中，直接返回即可；
復(fù)雜度分析：時間復(fù)雜度$O(n)$，空間復(fù)雜度$O(n)$

/**
 * 解法2:HashMap求解，時間復(fù)雜度O(n)，空間復(fù)雜度O(n)
 * 遍歷求兩數(shù)之和等于target，返回兩數(shù)下標(biāo)（從1開始）
 * http://www.lintcode.com/zh-cn/problem/two-sum/
 * @author yzwall
 */
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap map = new HashMap<>();
        int[] results = new int[2];
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                results[0] = map.get(nums[i]) + 1;
                results[1] = i + 1;
                break;
            }
            map.put(target - nums[i], i);
        }
        return results;
    }
}

解法3：雙指針$O(nlog(n))$時間復(fù)雜度求解

解題思路：首先將數(shù)組排序（時間復(fù)雜度$O(nlog(n))$），然后通過雙指針i和j分別從數(shù)組兩頭同時遍歷，保存數(shù)組排序前的元素位置可使用HashMap保存（空間復(fù)雜度$O(n)$），也可用輔助類保存（空間復(fù)雜度$O(1)$）；
復(fù)雜度分析：時間復(fù)雜度$O(nlog(n))$，空間復(fù)雜度$O(n)$ or $O(1)$；

/**
 * 解法3:HashMap + 雙指針求解，時間復(fù)雜度O(nlogn)，空間復(fù)雜度O(n)
 * 遍歷求兩數(shù)之和等于target，返回兩數(shù)下標(biāo)（從1開始）
 * http://www.lintcode.com/zh-cn/problem/two-sum/
 * @author yzwall
 */
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap> map = new HashMap<>();
        int[] results = new int[2];
        // HashMap用于記錄排序前數(shù)組元素對應(yīng)下標(biāo)
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.get(nums[i]).add(i);
                continue;
            }
            map.put(nums[i], new ArrayList());
            map.get(nums[i]).add(i);
        }
        
        int i = 0, j = nums.length - 1;
        // 排序后雙指針求解
        Arrays.sort(nums);
        while (i < j) {
            if (nums[i] + nums[j] == target) {
                int index1 = map.get(nums[i]).get(0);
                // 重復(fù)元素已經(jīng)訪問過一次，從對應(yīng)位置列表中剔除
                map.get(nums[i]).remove(0);
                int index2 = map.get(nums[j]).get(0);
                // 保證results[0] < result[1]
                results[0] = Math.min(index1, index2) + 1;
                results[1] = Math.max(index1, index2) + 1;
                return results;
            }
            if (nums[i] + nums[j] > target) {
                j--;
            } else {
                i++;
            }
        }
        return results;
    }
}

LintCode_587：兩數(shù)之和等于target的不重復(fù)組合數(shù)目

題目大意：給出未排序數(shù)組nums和指定目標(biāo)target，返回數(shù)組中兩數(shù)之和$= target$的所有不重復(fù)組合數(shù)；

解法：雙指針法$O(n)$時間復(fù)雜度求解

解題思路：數(shù)組排序后使用雙指針分別從起點(diǎn)和終點(diǎn)遍歷，如果存在$a + b = target$，則如果找到$a$所有組合方案，則$b$無需再找；
復(fù)雜度分析：時間復(fù)雜度$O(nlog(n))$，空間復(fù)雜度通過HashSet去重，耗費(fèi)額外空間$O(n)$(可優(yōu)化到$O(1)$)

/**
 * 雙指針找兩數(shù)和等于target的不重復(fù)組合數(shù)目，時間復(fù)雜度O(n)，空間復(fù)雜度O(n)
 * 求兩數(shù)之和等于target的所有不重復(fù)組合數(shù)目
 * http://www.lintcode.com/zh-cn/problem/two-sum-unique-pairs/
 * @author yzwall
 */
class Solution {
    public int twoSum6(int[] nums, int target) {
        int pairs = 0;
        if (nums == null || nums.length < 2) {
            return pairs;
        }
        Arrays.sort(nums);
        int i = 0;
        int j = nums.length - 1;
        HashSet set = new HashSet<>();
        while (i < j) {
            // 如果a + b = target, a找到后，b無需再找
            while (i < j && set.contains(nums[i])) {
                i++;
            }
            while (i < j && set.contains(nums[j])) {
                j--;
            }
            if (i < j) {
                if (nums[i] + nums[j] == target) {
                    set.add(nums[i]);
                    set.add(nums[j]);
                    pairs++;
                } else if (nums[i] + nums[j] > target) {
                    j--;
                } else {
                    i++;
                }
            }
        }
        return pairs;
    }
}

LintCode_608：兩數(shù)之和等于target（數(shù)組已排序）

題目大意：題目是LintCode_56的簡化版，解法1和解法2可直接使用；與解法1,2相比，解法3雙指針法充分利用數(shù)組已排序條件，時間復(fù)雜度降低到$O(n)$，空間復(fù)雜度降低到$O(1)$；

LintCode_443：兩數(shù)之和大于target

題目大意：求出數(shù)組nums中兩數(shù)之和$> target$的組合數(shù)目；

解法1：暴力$O(n^2)$時間復(fù)雜度求解

二重循環(huán)暴力求解；

解法2：雙指針法$O(nlog(n))$時間復(fù)雜度求解

解題思路：首先將數(shù)組nums升序排序，雙指針$i$從起點(diǎn)開始，指針$j$從終點(diǎn)開始，一旦有：$$nums[i] + nums[j] > target, $$則由于數(shù)組嚴(yán)格不遞減，$$forall numin[nums[i], nums[j]], num + nums[j] > target$$，因此執(zhí)行pairs += (j - i)，此時$nums[j]$所有方案搜索完畢，執(zhí)行j--；

復(fù)雜度分析：時間復(fù)雜度$O(nlog(n))$，空間復(fù)雜度$O(1)$

/**
 * 解法2：雙指針法求解，時間復(fù)雜度O(logn)，空間復(fù)雜度O(1) 
 * 求兩數(shù)之和大于target的組合數(shù)目
 * http://www.lintcode.com/en/problem/two-sum-greater-than-target/
 * @author yzwall
 */
class Solution {
     public int twoSum2(int[] nums, int target) {
            int pairs = 0;
            if (nums == null || nums.length < 2) {
                return pairs;
            }
            Arrays.sort(nums);
            int i = 0;
            int j = nums.length - 1;
            while (i < j) {
                if (nums[i] + nums[j] > target) {
                    pairs += j - i;
                    // nums[j]所有方案求解完畢，j--
                    j--;
                } else {
                    i++;
                }
            }
            return pairs;
     }
}

LintCode_609：兩數(shù)之和不超過target

題目大意：求出數(shù)組nums中兩數(shù)之和$leqslant target$的組合數(shù)目；

LintCode_610：兩數(shù)之差等于target 解法1：暴力$O(n^2)$時間復(fù)雜度求解

二重循環(huán)暴力求解；

解法2：雙指針法$O(nlog(n))$時間復(fù)雜度求解

解題思路：首先將數(shù)組nums升序排序，雙指針$i$從起點(diǎn)開始，指針$j$從終點(diǎn)開始，一旦有：$$nums[i] + nums[j] leq target, $$則由于數(shù)組嚴(yán)格不遞減，$$forall numin[nums[i], nums[j]], num + nums[j] leq target$$，因此執(zhí)行pairs += (j - i)，此時$nums[i]$所有方案搜索完畢，執(zhí)行i++；
復(fù)雜度分析：時間復(fù)雜度$O(nlog(n))$，空間復(fù)雜度$O(1)$

/**
 * 雙指針法求解，時間復(fù)雜度O(nlogn)，空間復(fù)雜度O(1)
 * 求兩數(shù)之和小于等于target的所有組合數(shù)目
 * http://www.lintcode.com/en/problem/two-sum-less-than-or-equal-to-target/
 * @author yzwall
 */
class Solution {
     public int twoSum5(int[] nums, int target) {
        int pairs = 0;
        if (nums == null || nums.length < 2) {
            return pairs;
        }
        Arrays.sort(nums);
        int i = 0;
        int j = nums.length - 1;
        while (i < j) {
            // nums[i]的所有組合 = j - i
            if (nums[i] + nums[j] <= target) {
                pairs += j - i;
                i++;
            } else {
                j--;
            }
        }
        return pairs;
     }
}

LintCode_533：兩數(shù)之和最接近target

題目大意：求出數(shù)組nums中兩數(shù)之和與target的最近距離（非負(fù)）；

解法1：暴力$O(n^2)$時間復(fù)雜度求解

解題思路：二重循環(huán)不斷迭代最小距離；
復(fù)雜度分析：時間復(fù)雜度$O(n^2)$，空間復(fù)雜度$O(1)$；

/**
 * 解法1：暴力時間復(fù)雜度O(n^2)
 * 求兩數(shù)之和最接近target，求最近距離
 * http://www.lintcode.com/en/problem/two-sum-closest-to-target/
 * @author yzwall
 */
class Solution {
    public int twoSumClosest(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return target;
        }
        
        int min = Integer.MAX_VALUE;
        int temp;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                temp = target - (nums[i] + nums[j]);
                min = Math.min(min, Math.abs(temp));
            }
        }
        return min;
    }
}

解法2：雙指針法$O(nlog(n))$時間復(fù)雜度求解

解題思路：首先將數(shù)組排序，雙指針分別從起點(diǎn)和終點(diǎn)遍歷，臨時距離
$$
temp = left | target - (nums[i] + nums[j]) right |
$$
不停與最短距離$min$比較迭代，$temp = 0$時直接返回；
復(fù)雜度分析：時間復(fù)雜度$O(nlog(n))$，空間復(fù)雜度$O(1)$；

/**
 * 解法2：雙指針法求解，時間復(fù)雜度O(nlogn)
 * 求兩數(shù)之和最接近target，求最近距離
 * http://www.lintcode.com/en/problem/two-sum-closest-to-target/
 * @author yzwall
 */
class Solution {
    public int twoSumClosest(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return target;
        }
        
        Arrays.sort(nums);
        int i = 0;
        int j = nums.length - 1;
        int min = Integer.MAX_VALUE;
        int temp;
        while (i < j) {
            temp = Math.abs(target - (nums[i] + nums[j]));
            if (temp == 0) {
                return 0;
            }
            min = Math.min(min, temp);
            if (nums[i] + nums[j] > target) {
                // 距離過大, j--
                j--;
            } else {
                // 距離過小, i++
                i++;
            }
        }
        return min;
   }
}

LintCode_610：兩數(shù)之差等于target 解法1：暴力$O(n^2)$時間復(fù)雜度求解

二重循環(huán)暴力求解；

解法2：雙指針法$O(nlog n)$時間復(fù)雜度求解

解題思路：首先將數(shù)組nums升序排序，雙指針$i$從起點(diǎn)開始，指針$j$從終點(diǎn)開始，一旦有：$$nums[i] + nums[j] leq target$$則由于數(shù)組嚴(yán)格不遞減，$$forall numin[nums[i], nums[j]], num + nums[j] leq target$$，因此執(zhí)行pairs += (j - i)，此時$nums[i]$所有方案搜索完畢，執(zhí)行i++；
復(fù)雜度分析：時間復(fù)雜度$O(nlog(n))$，空間復(fù)雜度$O(1)$

GPU云服務(wù)器云服務(wù)器變種一對多條件查詢問題 java多線程問題之和

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

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/70052.html

發(fā)表評論

登陸后可評論

0條評論

lentoo

男|高級講師

我要關(guān)注我要私信

TA的文章

如何下載tensorflow

閱讀 766·2023-04-25 17:33
Ubuntu系統(tǒng)手動編譯安裝LAMP Web網(wǎng)站環(huán)境的過程

閱讀 3626·2021-07-29 14:49
實(shí)現(xiàn)一個函數(shù)clone，可以對JavaScript中的5種主要的數(shù)據(jù)類型進(jìn)行值復(fù)制。

閱讀 2480·2019-08-30 15:53
事件循環(huán)(EventLoop)的學(xué)習(xí)總結(jié)

閱讀 3434·2019-08-29 16:27
前端每日實(shí)戰(zhàn)：91# 視頻演示如何用純 CSS 創(chuàng)作一個行駛中的火車 loader

閱讀 2000·2019-08-29 16:11
css垂直居中布局總結(jié)

閱讀 1029·2019-08-29 14:17
前端開發(fā)應(yīng)屆生面試指南（含各大公司具體指南及面試真題）

閱讀 2431·2019-08-29 13:47
20170917 前端開發(fā)周報:JavaScript函數(shù)式編程、作用域和閉包

閱讀 2016·2019-08-29 13:28

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

兩數(shù)之和問題各變種多解法小結(jié)

相關(guān)文章

**【前端來刷LeetCode】兩數(shù)之和與兩數(shù)相加**

**LeetCode - 001 - 兩數(shù)之和（two-sum）**

**LeetCode 167：兩數(shù)之和 II - 輸入有序數(shù)組 Two Sum II - Input a**

**LeetCode 167：兩數(shù)之和 II - 輸入有序數(shù)組 Two Sum II - Input a**

**【leetcode系列】001-兩數(shù)之和**

發(fā)表評論

0條評論

lentoo

男|高級講師

TA的文章

如何下載tensorflow

Ubuntu系統(tǒng)手動編譯安裝LAMP Web網(wǎng)站環(huán)境的過程

實(shí)現(xiàn)一個函數(shù)clone，可以對JavaScript中的5種主要的數(shù)據(jù)類型進(jìn)行值復(fù)制。

事件循環(huán)(EventLoop)的學(xué)習(xí)總結(jié)

前端每日實(shí)戰(zhàn)：91# 視頻演示如何用純 CSS 創(chuàng)作一個行駛中的火車 loader

css垂直居中布局總結(jié)

前端開發(fā)應(yīng)屆生面試指南（含各大公司具體指南及面試真題）

20170917 前端開發(fā)周報:JavaScript函數(shù)式編程、作用域和閉包

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

兩數(shù)之和問題各變種多解法小結(jié)

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！