「算法」两数之和 & 两数之和 II

00001 两数之和

题目描述

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9， 所以返回 [0, 1]

力扣地址

• https://leetcode.com/problems/two-sum
• https://leetcode-cn.com/problems/two-sum

解题报告

暴力法

本题解由微信公众号小猿刷题提供, 错误之处, 欢迎指正.

暴力法很简单，遍历每个元素 x，并查找是否存在一个值与 target−x 相等的目标元素.

/**
 *  微信公众号"小猿刷题"
 */
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

哈希表

本题解由微信公众号小猿刷题提供, 错误之处, 欢迎指正.

为了优化运行时间复杂度，引入哈希表来检查数组中是否存在目标元素。如果存在，则找出它的索引。

/**
 *  微信公众号"小猿刷题"
 */
class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 数字原始和其对应的下标映射
        Map<Integer, Integer> map = new HashMap<>();
        
        // Hash表中检测是否存在匹配
        for(int i=0; i< nums.length; i++){
            int num = target - nums[i];
            if(map.containsKey(num)){
                return new int[]{map.get(num), i};
            } else {
                map.put(nums[i], i);
            }
        }
        
        throw new IllegalArgumentException("No two sum solution");
    }
}

小猿刷题

00167 两数之和 II - 输入有序数组

题目描述

给定一个已按照 升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

• 返回的下标值( index1 和 index2 )不是从零开始的。
• 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

力扣地址

• https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
• https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

解题报告

哈希表

本题解由微信公众号小猿刷题提供, 错误之处, 欢迎指正.

遍历数组，数组遍历的当前值为 nums[i]，那么 y 应该是 target - nums[i]; 所以只要在遍历的时候确定 target - nums[i] 在数组里有，返回对应下标.

/**
 *  微信公众号"小猿刷题"
 */
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap();
        for(int i = 0; i < nums.length; i ++){
            int cur = nums[i];
            int num = target - cur;
            if(map.containsKey(num)){
                return new int[] {map.get(num) + 1, i + 1};
            } else {
                map.put(cur, i);
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

双指针

本题解由微信公众号小猿刷题提供, 错误之处, 欢迎指正.

我们使用两个指针，初始分别位于第一个元素和最后一个元素位置，比较这两个元素之和与目标值的大小。

如果和等于目标值，我们发现了这个唯一解。如果比目标值小，我们将较小元素指针增加一。如果比目标值大，我们将较大指针减小一。移动指针后重复上述比较知道找到答案。

/**
 *  微信公众号"小猿刷题"
 */
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            if (nums[low] + nums[high] == target) {
                return new int[] {low + 1, high + 1};
            }
            if (nums[low] + nums[high] < target) {
                low ++;
            } else {
                high --;
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

小猿刷题