两数之和问题各变种多解法小结

lentoo 发布于2019-08-16 10:34 / 471人阅读

摘要：两数之和问题各变种多解法小结声明文章均为本人技术笔记，转载请注明出处两数之和等于题目大意给出未排序数组和指定目标，返回数组中两数之和的组合元素下标要求下标从开始，而且，保证题目中有且只有个可行解解法暴力时间复杂度求解解题思路暴力二重循环求解

两数之和问题各变种多解法小结 声明

文章均为本人技术笔记，转载请注明出处：
[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多线程问题之和

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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