兩數之和問題各變種多解法小結

lentoo 發布于2019-08-16 10:34 / 533人閱讀

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

兩數之和問題各變種多解法小結 聲明

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

LintCode_56：兩數之和等于target

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

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

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

/**
 * 解法1:時間復雜度O(n^2)，空間復雜度O(1)
 * 遍歷求兩數之和等于target，返回兩數下標（從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)$時間復雜度求解

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

/**
 * 解法2:HashMap求解，時間復雜度O(n)，空間復雜度O(n)
 * 遍歷求兩數之和等于target，返回兩數下標（從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))$時間復雜度求解

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

/**
 * 解法3:HashMap + 雙指針求解，時間復雜度O(nlogn)，空間復雜度O(n)
 * 遍歷求兩數之和等于target，返回兩數下標（從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用于記錄排序前數組元素對應下標
        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);
                // 重復元素已經訪問過一次，從對應位置列表中剔除
                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：兩數之和等于target的不重復組合數目

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

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

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

/**
 * 雙指針找兩數和等于target的不重復組合數目，時間復雜度O(n)，空間復雜度O(n)
 * 求兩數之和等于target的所有不重復組合數目
 * 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：兩數之和等于target（數組已排序）

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

LintCode_443：兩數之和大于target

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

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

二重循環暴力求解；

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

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

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

/**
 * 解法2：雙指針法求解，時間復雜度O(logn)，空間復雜度O(1) 
 * 求兩數之和大于target的組合數目
 * 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：兩數之和不超過target

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

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

二重循環暴力求解；

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

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

/**
 * 雙指針法求解，時間復雜度O(nlogn)，空間復雜度O(1)
 * 求兩數之和小于等于target的所有組合數目
 * 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：兩數之和最接近target

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

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

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

/**
 * 解法1：暴力時間復雜度O(n^2)
 * 求兩數之和最接近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))$時間復雜度求解

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

/**
 * 解法2：雙指針法求解，時間復雜度O(nlogn)
 * 求兩數之和最接近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：兩數之差等于target 解法1：暴力$O(n^2)$時間復雜度求解

二重循環暴力求解；

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

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

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

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

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

【前端來刷LeetCode】兩數之和與兩數相加

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

BLUE 2019-08-26 13:53 評論0 收藏0
LeetCode - 001 - 兩數之和（two-sum）

摘要：解法返回目錄解題代碼執行測試解題思路使用雙重循環破解。解法返回目錄解題代碼執行測試知識點遍歷數組，返回遍歷項，返回當前索引。 Create by jsliang on 2019-05-16 22:19:13 Recently revised in 2019-05-17 14:22:40 Hello 小伙伴們，如果覺得本文還不錯，記得給個 star ，小伙伴們的 star 是我持續更新的動...

habren 2019-05-23 17:27 評論0 收藏0
LeetCode 167：兩數之和 II - 輸入有序數組 Two Sum II - Input a

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

張春雷 2019-08-16 18:29 評論0 收藏0
LeetCode 167：兩數之和 II - 輸入有序數組 Two Sum II - Input a

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

Me_Kun 2019-07-31 11:26 評論0 收藏0
【leetcode系列】001-兩數之和

摘要：題意給定一個整數數組和一個目標值，請你在該數組中找出和為目標值的那兩個整數，并返回他們的數組下標。也就是說，字典里記錄的是每個數據希望找到的另一半的值的大小。返回這兩個下標就行，如果沒有存在于字典里，那么繼續存入字典。 showImg(https://segmentfault.com/img/bVbvgPA); 題意：給定一個整數數組 nums 和一個目標值 target，請你在該數...

EddieChan 2019-08-26 10:12 評論0 收藏0